Мала теорема Ферма

Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах.

Формулювання

Мала теорема Ферма допускає кілька еквівалентних формулювань.

Нехай $\ p$ — просте, $\ a$ — ціле, що не ділиться на $\ p$. Тоді:

$\ a^{p-1} \equiv 1 \pmod{p}$.

Еквівалентним є наступне твердження:

Нехай $\ p$ — просте, $\ a$ — довільне ціле число. Тоді:

$\ a^p - a \equiv 0 \pmod p$.

Узагальнення 1

Ейлером було доведено, що для довільного $\ a$ взаємно простого з $\ m>1$ виконується наступне:

$a^{\varphi \left ( m \right )} \equiv 1 \pmod{m} \!$

де $\varphi \left ( m \right ) \!$ — функція Ейлера.

Узагальнення 2

Рівність $x^q=x \!$ справедлива для всіх елементів $\ x$ скінченного поля $k_q \!$, утвореного $\ q$ елементами.

Доведення

Доведення 1 (за методом математичної індукції)

Позначимо, як звично

${p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!}$ — біноміальний коефіцієнт.

Тоді для простого $\ p$ і $\ 0<k<p$ маємо, що ${p \choose k}$ ділиться на $\ p$. Справді можна записати ${p \choose k}= \frac{pm}{k!}\quad\quad,$ де $\quad\quad m=(p-1)(p-2)\cdots (p-k+1)$. Оскільки $\ p$ і $\ k!$ є взаємно-простими, то, очевидно, що $\ k!$ ділить $\ m$ і, як наслідок ${p \choose k}$ ділиться на $\ p$. Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для $\ a=1$. Припустимо, що вона справджується для певного цілого $\ a$. Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:

$(a+1)^p \equiv a^p + a^0 + \sum_{k=1}^{p-1}{p \choose k}a^k \equiv a^p + 1 \equiv a + 1\pmod{p}$.

тобто $(a+1)^p - (a+1) \equiv 0 \pmod p$, що доводить твердження для додатніх цілих. Для від'ємних доведення аналогічне.

Доведення 2 (використовуючи лишки)

Припустимо, що $\ a$ додатнє число, що не ділиться на $\ p$. Якщо записати

$a, 2a, 3a, \ldots, (p-1)a \quad\quad$

і обрахувати одержану послідовність за модулем $\ p$, то ми отримаємо деяку перестановку чисел:

$1, 2, 3, \ldots, p-1. \quad\quad\quad$.

Справді, жодне з чисел $a, 2a, 3a, \ldots, (p-1)a$ не ділиться на $\ p$, оскільки і $\ a$ і будь-яке з чисел $1, 2, 3, \ldots, p-1.$ є взаємно прості з $\ p$. Далі всі числа $a, 2a, \ldots,(p-1)a$ мають бути відмінними одне від одного за модулем $\ p$. Справді, якщо

$ka \equiv ma \pmod p, \,\!$

де $\ k$ і $\ m$ належать множині чисел $1, 2,\ldots, (p-1)$ то, зважаючи на взаємну простоту $\ a$ і $\ p$ отримуємо:

$k \equiv m \pmod p. \,\!$, що неможливо.

Відповідно, якщо ми перемножимо обидві послідовності, то результати повинні бути еквівалентні за модулем $\ p$:

$a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots (p-1) \pmod p.$

Після перестановки множників і перепозначення отримуємо:

$\ a^{p-1} (p-1)! \equiv (p-1)! \pmod p.$

Остаточно, зважаючи, що $\ p$ і $\ (p-1)!$ взаємно-прості одержуємо твердження теореми:

$a^{p-1} \equiv 1 \pmod p.\,\!$

Доведення 3 (комбінаторне)

Припустимо, що ми маємо бусинки $\ a$ різних кольорів і нам потрібно зробити з них намисто довжиною $\ p$ бусинок. Для початку зробимо стрічку з $\ p$ бусинок. Існує $\ a^p$ різних стрічок. Відкинемо всі однотонні стрічки їх всього $\ a$. Залишеться $\ a^p-a$ різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує $\ p$ різних циклічних перестановок то існує $\ \frac{a^p-a}{p}$ різних намист. Виходячи з інтерпретації числа $\ \frac{a^p-a}{p}$ воно ціле.

Див. також

• Числа Кармайкла - псевдопрості числа
• Теорема Ферма
• Теорема Ферма (велика)

Джерела

• Ойстин Оре (2003). Приглашение в теорию чисел. Москва: Едиториал УРСС. ISBN 5-354-00252-4. 

• Arthur Engel (1997). Problem-Solving Strategies. New York: Springer-Verlag. ISBN 0-387-98219-1.