Теорема Ейлера (теорія чисел)
Теорема Ейлера — одне з основних тверджень елементарної теорії чисел стверджує, що
якщо і взаємно_прості, то ,
де — функція Ейлера.
Частковим випадком теореми Ейлера при простому є мала теорема Ферма.
В свою чергу теорема Ейлера є частковим випадком теореми Лагранжа.
Доведення
Нехай — всі натуральні числа, менші і взаємно прості з ним.
Розглянем всеможливі добутки для всіх від до .
Оскільки взаємно просте з і взаємно прості з , то і також взаємно прості з , тобто для деякого .
Далі маємо, що всі остачі від ділення на відмінні. Справді, нехай це не так, тобто існують такі , що
- .
Тоді .
Оскільки взаємно просте з , то остання рівність рівносильна тому, що
- або .
Це неможливо, оскільки числа попарно відмінні по модулю .
Перемножимо всі рівності . Одержуємо:
або
- .
Так як число взаємно просте з , то остання рівність рівносильна тому, що
- або .
Застосування
За допомогою даної теореми можна легко обчислювати модуль великих степенів. Наприклад, ми хочемо обчислити 7222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4. Отже, згідно з теоремою Ейлера 74 ≡ 1 (mod 10) і як наслідок 7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10).
Теорема Ейлера є також теоретичною основою криптографічної системи RSA.
Література
- Чандрасекхаран К. Введение в аналитическую теорию чисел. — Москва : Мир, 1974. — 187 с.(рос.)
- Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
- Трост Э. Простые числа, пер. с нем., М., 1959