Перейти до вмісту

Теорема Ейлера (теорія чисел)

Очікує на перевірку
Матеріал з Вікіпедії — вільної енциклопедії.

Теорема Ейлера (Ойлера) — одне з основних тверджень елементарної теорії чисел стверджує, що

якщо і взаємно_прості, то ,

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

Частковим випадком теореми Ейлера при простому є мала теорема Ферма.

В свою чергу теорема Ейлера є частковим випадком теореми Лагранжа.

Доведення

[ред. | ред. код]

Нехай — всі натуральні числа, менші і взаємно прості з ним.

Розглянем всеможливі добутки для всіх від до .

Оскільки взаємно просте з і взаємно прості з , то і також взаємно прості з , тобто для деякого .

Далі маємо, що всі остачі від ділення на відмінні. Справді, нехай це не так, тобто існують такі , що

.

Тоді .

Оскільки взаємно просте з , то остання рівність рівносильна тому, що

або .

Це неможливо, оскільки числа попарно відмінні по модулю .

Перемножимо всі рівності . Одержуємо:

або

.

Так як число взаємно просте з , то остання рівність рівносильна тому, що

або .

Застосування

[ред. | ред. код]

За допомогою даної теореми можна легко обчислювати модуль великих степенів. Наприклад, ми хочемо обчислити 7222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4. Отже, згідно з теоремою Ейлера 74 ≡ 1 (mod 10) і як наслідок 7222 ≡ 74x55 + 2 ≡ (74)55x72 ≡ 155x72 ≡ 49 ≡ 9 (mod 10).

Теорема Ейлера є також теоретичною основою криптографічної системи RSA.

Література

[ред. | ред. код]

Українською

[ред. | ред. код]
  • (укр.) Гаврилків В. М. Елементи теорії груп та теорії кілець. — І.-Ф.  : Голіней, 2023. — 153 с.

Іншими мовами

[ред. | ред. код]