Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга [en] 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах.
Формулювання
Мала теорема Ферма допускає кілька еквівалентних формулювань.
Нехай — просте,
— ціле, що не ділиться на
. Тоді:
.
Еквівалентним є наступне твердження: Нехай — просте,
— довільне ціле число. Тоді:
.
Узагальнення 1
Ейлером було доведено, що для довільного взаємно простого з
виконується наступне:
де — функція Ейлера.
Узагальнення 2
Рівність справедлива для всіх елементів
скінченного поля
, утвореного
елементами.
Доведення
Доведення 1 (за методом математичної індукції)
Позначимо, як звично
Тоді для простого і
маємо, що
ділиться на
. Справді можна записати
де
. Оскільки
і
є взаємно-простими, то, очевидно, що
ділить
і, як наслідок
ділиться на
. Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для
. Припустимо, що вона справджується для певного цілого
. Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:
.
тобто , що доводить твердження для додатних цілих. Для від'ємних доведення аналогічне.
Доведення 2 (використовуючи лишки)
Припустимо, що додатне число, що не ділиться на
. Якщо записати
і обрахувати одержану послідовність за модулем , то ми отримаємо деяку перестановку чисел:
.
Справді, жодне з чисел не ділиться на
, оскільки і
і будь-яке з чисел
є взаємно прості з
. Далі всі числа
мають бути відмінними одне від одного за модулем
. Справді, якщо
де і
належать множині чисел
то, зважаючи на взаємну простоту
і
отримуємо:
, що неможливо.
Відповідно, якщо ми перемножимо обидві послідовності, то результати повинні бути еквівалентні за модулем :
Після перестановки множників і перепозначення отримуємо:
Остаточно, зважаючи, що і
взаємно-прості одержуємо твердження теореми:
Доведення 3 (комбінаторне)
Припустимо, що ми маємо намистинки різних кольорів і нам потрібно зробити з них намисто довжиною
намистинок. Для початку зробимо стрічку з
намистинок. Існує
різних стрічок. Відкинемо всі однотонні стрічки їх всього
. Залишається
різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує
різних циклічних перестановок то існує
різних намист. Виходячи з інтерпретації числа
воно ціле.
Див. також
- (Числа Кармайкла) — псевдопрості числа
- (Теорема Ферма)
- (Теорема Ферма (велика))
Джерела
- Ойстин Оре (2003). Приглашение в теорию чисел. Москва: Едиториал УРСС. ISBN .
- Arthur Engel (1997). Problem-Solving Strategies. New York: Springer-Verlag. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет