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

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

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

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

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

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

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

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

${\displaystyle (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}}}$.

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

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

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

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

${\displaystyle 1,2,3,\ldots ,p-1.\quad \quad \quad }$.

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

${\displaystyle ka\equiv ma{\pmod {p}},\,\!}$

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

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

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

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

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

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

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

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

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