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

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

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

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

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

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

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

Доведення

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

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

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

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

Якщо записати

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

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

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

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

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

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

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

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

Див. також Числа Кармайкла — псевдопрості числа Теорема Ферма Теорема Ферма (велика)

Джерела