Теорема (Ферма). Нехай р – просте число, р не ділить a. Тоді:

a^p-1 º 1(mod p) .

Доказ 1. Нехай в умові теореми Ейлера m=p, тоді j(m)=p-1 (див. пункт 14 ). Одержуємо a^p-1 º 1(mod p).

Необхідно відзначити важливість умови взаємної простоти модуля і числа a у формулюваннях теорем Ейлера і Ферма. Простий приклад: порівняння 6² º 1(mod 3) очевидно не виконується. Однак можна легко підправити формулювання теореми Ферма, щоб зняти обмеження взаємної простоти.

Наслідок 1. Без всяких обмежень на a Î Z,

a^p º a(mod p) .

Доказ. Помножимо обидві частини порівняння a^p-1 º 1(mod p) на a. Зрозуміло, що вийде порівняння, справедливе і при a, кратному р.

Звичайно, доказ 1 теореми Ферма вийшов настільки коротким завдяки проведеній могутній попередній підготовці (доведена теорема Ейлера і вивчені властивості функції j(m)). Наведемо ще один варіант доказу теореми Ферма.

Доказ 2. Оскільки р - просте число, то всі біноміальні коефіцієнти (крім C₀^p і C_p^p) діляться на р, тому що чисельник виписаного виразу містить р, а знаменник не містить цього множника. Якщо згадати біном Ньютона, то стає зрозуміло, що різниця (A+B)^p-A^p -B^p= =C_p¹A^p-1B¹+C_p²A^p-2B²+...+C_p^p-2A²B^p-2+C_p^p-1A¹B^p-1, де А і В – довільні цілі числа, завжди ділиться на р. Послідовним застосуванням цього спостереження одержуємо, що (A+B+C)^p--A^p-B^p-C^p={[(A+B)+C]^p-(A+B)^p-C^p}+(A+B)^p -A^p -B^p завжди ділиться на р; (A+B+C+D)^p-A^p–B^p -C^p-D^p завжди ділиться на р; і взагалі, (A+B+C+...+K)^p -A^p-B^p-C^p-...-K^p завжди ділиться на р. Нехай A=B=C=...=K=1 і візьмемо кількість цих чисел рівним a. Вийде, що a^p-a ділиться на р, а це і є теорема Ферма в більш загальному формулюванні.

Наслідок 2. (a+b)^p º a^p +b^p (mod p).

Наведемо кілька прикладів застосування теорем Ферма і Ейлера. Зазначимо, що ефективність застосування теорем Ферма і Ейлера ґрунтується на тому, що порівняння, що даються цими теоремами, зручно підносити до степеня, оскільки справа у них стоїть одиниця, що на піднесення до степеня не реагує.

Приклад 2. Довести, що 1¹⁸ +2¹⁸ +3¹⁸ +4¹⁸ +5¹⁸ +6¹⁸ º -1(mod 7)

Доказ. Числа 1, 2, 3, 4, 5, 6 взаємно прості з 7. За теоремою Ферма маємо:

Піднесемо ці порівняння до кубу і додамо:

1¹⁸ +2¹⁸ +3¹⁸ +4¹⁸ +5¹⁸ +6¹⁸ º 6(mod 7) º -1(mod 7)

Приклад 3. Знайти залишок ділення 7⁴⁰² на 101.

Рішення. Число 101 – просте, (7, 101)=1, отже, за теоремою Ферма: 7¹⁰⁰º1(mod 101). Піднесемо це порівняння до четвертої степені: 7⁴⁰⁰º1(mod 101), домножимо його на очевидне порівняння 7²º49(mod 101), одержимо: 7⁴⁰²º 49(mod 101). Виходить, що залишок ділення 7⁴⁰² на 101 дорівнює 49.

Приклад 5. Довести, що (73¹² -1) поділяється на 105.

Рішення. Маємо: 105=3 × 5 × 7, (73,3)=(73,5)=(73,7)=1. По теоремі Ферма:

73² º 1(mod 3)

73⁴ º 1(mod 5)

73⁶ º 1(mod 7)

Перемножуючи, одержуємо:

73¹² º 1(mod 3),(mod 5),(mod 7),

звідки, за властивостями порівнянь, з пункту 16, випливає:

73¹² -1 º 0(mod 105),