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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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