Теорема Ейлера (Ойлера) — одне з основних тверджень елементарної теорії чисел стверджує, що
якщо
і
взаємно_прості, то
,
де
— функція Ейлера.
Частковим випадком теореми Ейлера при простому
є мала теорема Ферма.
В свою чергу теорема Ейлера є частковим випадком теореми Лагранжа.
Доведення
Нехай
— всі натуральні числа, менші
і взаємно прості з ним.
Розглянем всеможливі добутки
для всіх
від
до
.
Оскільки
взаємно просте з
і
взаємно прості з
, то і
також взаємно прості з
, тобто
для деякого
.
Далі маємо, що всі остачі від ділення
на
відмінні. Справді, нехай це не так, тобто існують такі
, що
.
Тоді
.
Оскільки
взаємно просте з
, то остання рівність рівносильна тому, що
або
.
Це неможливо, оскільки числа
попарно відмінні по модулю
.
Перемножимо всі рівності
. Одержуємо:

або
.
Так як число
взаємно просте з
, то остання рівність рівносильна тому, що
або
.
Застосування
За допомогою даної теореми можна легко обчислювати модуль великих степенів. Наприклад, ми хочемо обчислити 7222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4. Отже, згідно з теоремою Ейлера 74 ≡ 1 (mod 10) і як наслідок 7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10).
Теорема Ейлера є також теоретичною основою криптографічної системи RSA.
Література
Українською
- (укр.) Гаврилків В. М. Елементи теорії груп та теорії кілець. — : Голіней, 2023. — 153 с.
Іншими мовами