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

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

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

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

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

$a^{p-1}\equiv 1(\mathrm{mod}p)$.

Еквівалентним є наступне твердження: Нехай $p$ — просте, $a$ — довільне ціле число. Тоді:

$a^p-a\equiv 0(\mathrm{mod}p)$.

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

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

$a^{\phi \left(m\right)}\equiv 1(\mathrm{mod}m)$

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

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

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

Доведення

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

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

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

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

$(a+1{)}^p\equiv a^p+a^0+\sum _{k=1}^{p-1}(\genfrac{}{}{0ex}{}{p}{k})a^k\equiv a^p+1\equiv a+1(\mathrm{mod}p)$.

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

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

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

$a,2a,3a,\dots ,(p-1)a$

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

$1,2,3,\dots ,p-1.$.

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

$ka\equiv ma(\mathrm{mod}p),$

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

$k\equiv m(\mathrm{mod}p).$, що неможливо.

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

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

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

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

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

$a^{p-1}\equiv 1(\mathrm{mod}p).$

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

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

Див. також

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

Джерела

• Шаблон:Cite book

• Шаблон:Cite book