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

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

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

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

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

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

Доведення

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

Розглянем всеможливі добутки $a{x}_i$ для всіх $i$ від $1$ до $\phi (m)$.

Оскільки $a$ взаємно просте з $m$ і $x_i$ взаємно прості з $m$, то і $a{x}_i$ також взаємно прості з $m$, тобто $a{x}_i\equiv x_j(\mathrm{mod}m)$ для деякого $j$.

Далі маємо, що всі остачі від ділення $a{x}_i$ на $m$ відмінні. Справді, нехай це не так, тобто існують такі $i_1\ne i_2$, що

$a{x}_{i_1}\equiv a{x}_{i_2}(\mathrm{mod}m)$.

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

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

$x_{i_1}-x_{i_2}\equiv 0(\mathrm{mod}m)$ або $x_{i_1}\equiv x_{i_2}(\mathrm{mod}m)$.

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

Перемножимо всі рівності $a{x}_i\equiv x_j(\mathrm{mod}m)$. Одержуємо:

$x_1...x_{\phi (m)}{a}^{\phi (m)}=x_1...x_{\phi (m)}(\mathrm{mod}m)$

або

$x_1...x_{\phi (m)}(a^{\phi (m)}-1)=0(\mathrm{mod}m)$.

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

$a^{\phi (m)}-1=0(\mathrm{mod}m)$ або $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$.

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

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

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

Література

Українською

• Шаблон:Ref-uk Шаблон:Книга

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

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