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

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

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

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

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

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

Доведення

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

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

Оскільки ${\displaystyle a}$ взаємно просте з ${\displaystyle m}$ і ${\displaystyle x_{i}}$ взаємно прості з ${\displaystyle m}$, то і ${\displaystyle ax_{i}}$ також взаємно прості з ${\displaystyle m}$, тобто ${\displaystyle ax_{i}\equiv x_{j}{\pmod {m}}}$ для деякого ${\displaystyle j}$.

Далі маємо, що всі остачі від ділення ${\displaystyle ax_{i}}$ на ${\displaystyle m}$ відмінні. Справді, нехай це не так, тобто існують такі ${\displaystyle i_{1}\neq i_{2}}$, що

${\displaystyle ax_{i_{1}}\equiv ax_{i_{2}}{\pmod {m}}}$.

Тоді ${\displaystyle a(x_{i_{1}}-x_{i_{2}})\equiv 0{\pmod {m}}}$.

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

${\displaystyle x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}}$ або ${\displaystyle x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}}$.

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

Перемножимо всі рівності ${\displaystyle ax_{i}\equiv x_{j}{\pmod {m}}}$. Одержуємо:

${\displaystyle x_{1}...x_{\varphi (m)}a^{\varphi (m)}=x_{1}...x_{\varphi (m)}{\pmod {m}}}$

або

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

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

${\displaystyle a^{\varphi (m)}-1=0{\pmod {m}}}$ або ${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {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.

Література

Українською

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

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

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