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

Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 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.