Відкрити головне меню

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

ФормулюванняРедагувати

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

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

 .

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

 .

Узагальнення 1Редагувати

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

 

де   — функція Ейлера.

Узагальнення 2Редагувати

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

ДоведенняРедагувати

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

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

  — біноміальний коефіцієнт.

Тоді для простого   і   маємо, що   ділиться на  . Справді можна записати   де  . Оскільки   і   є взаємно-простими, то, очевидно, що   ділить   і, як наслідок   ділиться на  . Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для  . Припустимо, що вона справджується для певного цілого  . Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:

 .

тобто  , що доводить твердження для додатніх цілих. Для від'ємних доведення аналогічне.

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

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

 

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

 .

Справді, жодне з чисел   не ділиться на  , оскільки і   і будь-яке з чисел   є взаємно прості з  . Далі всі числа   мають бути відмінними одне від одного за модулем  . Справді, якщо

 

де   і   належать множині чисел   то, зважаючи на взаємну простоту   і   отримуємо:

 , що неможливо.

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

 

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

 

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

 

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

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

Див. такожРедагувати

ДжерелаРедагувати

  • Ойстин Оре (2003). Приглашение в теорию чисел. Москва: Едиториал УРСС. ISBN 5-354-00252-4. 
  • Arthur Engel (1997). Problem-Solving Strategies. New York: Springer-Verlag. ISBN 0-387-98219-1.