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