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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

якщо \ a і \ m взаємно_прості, то a^{\varphi(m)} \equiv 1 \pmod m,

де \varphi(m)функція Ейлера.

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

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

Доведення[ред.ред. код]

Нехай x_1,...,x_{\varphi(m)} — всі натуральні числа, менші m і взаємно прості з ним.

Розглянем всеможливі добутки ax_i для всіх i від 1 до \varphi(m).

Оскільки a взаємно просте з m і x_i взаємно прості з m, то і ax_i також взаємно прості з m, тобто ax_i \equiv x_j\pmod m для деякого j.

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

ax_{i_1}  \equiv ax_{i_2}\pmod m.

Тоді a(x_{i_1} - x_{i_2})  \equiv 0\pmod m.

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

x_{i_1} - x_{i_2} \equiv 0\pmod m або x_{i_1} \equiv x_{i_2}\pmod m.

Це неможливо, оскільки числа x_1,...,x_{\varphi(m)} попарно відмінні по модулю m.

Перемножимо всі рівності ax_i  \equiv x_j\pmod m. Одержуємо:

x_1 ... x_{\varphi(m)} a^{\varphi(m)} = x_1 ... x_{\varphi(m)}\pmod m

або

x_1 ... x_{\varphi(m)} (a^{\varphi(m)}-1) = 0\pmod m.

Так як число x_1 ... x_{\varphi(m)}\pmod m взаємно просте з m, то остання рівність рівносильна тому, що

a^{\varphi(m)}-1 = 0\pmod m або a^{\varphi(m)} \equiv 1\pmod m.

Застосування[ред.ред. код]

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

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

Література[ред.ред. код]

  • Чандрасекхаран. Введение в аналитическую теорию чисел.
  • Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
  • Трост Э. Простые числа, пер. с нем., М., 1959