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

Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.