Теорема Эйлера

Теорема Эйлера — фундаментальное утверждение теории чисел, устанавливающее связь между показательной функцией и функцией Эйлера. В своей классической формулировке теорема гласит: если \(a\) и \(n\) — взаимно простые натуральные числа (то есть \(\gcd(a, n) = 1\)), то \(a^{\varphi(n)} \equiv 1 \pmod{n}\), где \(\varphi(n)\) — функция Эйлера, равная количеству натуральных чисел, не превосходящих \(n\) и взаимно простых с \(n\). Теорема является обобщением малой теоремы Ферма на случай составного модуля и играет ключевую роль в современной криптографии, в частности, в алгоритме RSA.

История

Теорема была впервые доказана швейцарским, немецким и российским математиком Леонардом Эйлером в 1736 году. Эйлер опубликовал её в работе «Theoremata arithmetica nova methodo demonstrata» (Новые теоремы арифметики, доказанные новым методом). Первоначально Эйлер сформулировал утверждение для случая, когда модуль \(n\) является простым числом; это частный случай известен как малая теорема Ферма. Позднее, в 1763 году, Эйлер обобщил результат на произвольный натуральный модуль, введя функцию \(\varphi(n)\) (часто называемую фи-функцией Эйлера). Доказательство Эйлера основывалось на свойствах вычетов по модулю \(n\) и использовало понятие приведённой системы вычетов.

Формулировка и обозначения

Пусть \(n\) — натуральное число, большее 1, и \(\varphi(n)\) — функция Эйлера. Для любого целого числа \(a\), взаимно простого с \(n\) (то есть \(\gcd(a, n) = 1\)), выполняется сравнение:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

Если \(n = 1\), то \(\varphi(1) = 1\), и сравнение \(a^{1} \equiv 1 \pmod{1}\) тривиально выполняется для любого \(a\), так как любое целое число сравнимо с 0 по модулю 1, а \(1 \equiv 0 \pmod{1}\). В практических приложениях обычно рассматривают \(n \ge 2\).

Функция Эйлера

Функция Эйлера \(\varphi(n)\) определяется как количество целых чисел \(k\) в интервале \(1 \le k \le n\), для которых \(\gcd(k, n) = 1\). Для простого числа \(p\) имеем \(\varphi(p) = p - 1\). Для степени простого числа \(p^k\) (\(k \ge 1\)) выполняется \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)\). Функция мультипликативна: если \(m\) и \(n\) взаимно просты, то \(\varphi(mn) = \varphi(m) \varphi(n)\). Например, \(\varphi(10) = \varphi(2) \cdot \varphi(5) = 1 \cdot 4 = 4\) (числа 1, 3, 7, 9).

Доказательство

Существует несколько классических доказательств теоремы Эйлера. Наиболее распространённое основано на свойствах приведённой системы вычетов.

Доказательство через приведённую систему вычетов

1. Пусть \(n\) — натуральное число, большее 1. Рассмотрим множество \(R = \{r_1, r_2, \dots, r_{\varphi(n)}\}\) всех натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это множество называется приведённой системой вычетов по модулю \(n\).
2. Умножим каждый элемент \(r_i\) на число \(a\), взаимно простое с \(n\). Получим множество \(aR = \{a r_1, a r_2, \dots, a r_{\varphi(n)}\}\). Все числа \(a r_i\) также взаимно просты с \(n\) (так как произведение двух чисел, взаимно простых с \(n\), взаимно просто с \(n\)). Кроме того, они попарно не сравнимы по модулю \(n\): если \(a r_i \equiv a r_j \pmod{n}\), то, сокращая на \(a\) (что возможно, так как \(a\) обратим по модулю \(n\)), получаем \(r_i \equiv r_j \pmod{n}\), что противоречит выбору \(r_i\).
3. Таким образом, множество \(aR\) по модулю \(n\) является перестановкой множества \(R\). Следовательно, произведение всех элементов \(aR\) сравнимо с произведением всех элементов \(R\) по модулю \(n\):

\[ \prod_{i=1}^{\varphi(n)} (a r_i) \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}. \]

1. Вынесем \(a\) за знак произведения в левой части:

\[ a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} r_i \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}. \]

1. Так как все \(r_i\) взаимно просты с \(n\), их произведение \(\prod r_i\) также взаимно просто с \(n\). Следовательно, на него можно сократить обе части сравнения:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

Доказательство через малую теорему Ферма и китайскую теорему об остатках

Другой подход использует разложение модуля \(n\) на простые множители. Если \(n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}\), то для каждого простого множителя \(p_i\) из условия \(\gcd(a, n) = 1\) следует \(\gcd(a, p_i^{k_i}) = 1\). По малой теореме Ферма для простого числа \(p_i\) имеем \(a^{p_i - 1} \equiv 1 \pmod{p_i}\). Обобщение на степень простого числа даёт \(a^{\varphi(p_i^{k_i})} \equiv 1 \pmod{p_i^{k_i}}\). Поскольку \(\varphi(n)\) является наименьшим общим кратным \(\varphi(p_i^{k_i})\), то \(a^{\varphi(n)} \equiv 1 \pmod{p_i^{k_i}}\) для всех \(i\). По китайской теореме об остатках отсюда следует \(a^{\varphi(n)} \equiv 1 \pmod{n}\).

Следствия и обобщения

Малая теорема Ферма

Если \(n = p\) — простое число, то \(\varphi(p) = p - 1\), и теорема Эйлера сводится к малой теореме Ферма: для любого целого \(a\), не кратного \(p\), \(a^{p-1} \equiv 1 \pmod{p}\).

Теорема Кармайкла

Функция Кармайкла \(\lambda(n)\) даёт наименьший положительный показатель, для которого \(a^{\lambda(n)} \equiv 1 \pmod{n}\) для всех \(a\), взаимно простых с \(n\). \(\lambda(n)\) делит \(\varphi(n)\), но может быть строго меньше. Например, для \(n = 8\): \(\varphi(8) = 4\), но \(\lambda(8) = 2\), так как \(3^2 = 9 \equiv 1 \pmod{8}\), \(5^2 = 25 \equiv 1 \pmod{8}\), \(7^2 = 49 \equiv 1 \pmod{8}\).

Обобщение на кольца вычетов

Теорема Эйлера является частным случаем более общего утверждения: в мультипликативной группе обратимых элементов кольца вычетов \(\mathbb{Z}_n^\times\) порядок любого элемента делит порядок группы, равный \(\varphi(n)\). Это следует из теоремы Лагранжа в теории групп.

Применение

Криптография (RSA)

Наиболее известное применение теоремы Эйлера — в криптосистеме с открытым ключом RSA, разработанной Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом в 1977 году. Алгоритм RSA основан на следующем:

• Выбираются два больших простых числа \(p\) и \(q\). Вычисляется модуль \(n = p \cdot q\).
• Вычисляется функция Эйлера \(\varphi(n) = (p-1)(q-1)\).
• Выбирается открытая экспонента \(e\), взаимно простая с \(\varphi(n)\). Обычно \(e = 65537\).
• Вычисляется секретная экспонента \(d\) как обратный элемент к \(e\) по модулю \(\varphi(n)\): \(e \cdot d \equiv 1 \pmod{\varphi(n)}\).

Шифрование сообщения \(m\) (представленного как число, меньшее \(n\) и взаимно простое с \(n\)) выполняется как \(c = m^e \mod n\). Расшифрование: \(m = c^d \mod n\). Корректность расшифрования следует из теоремы Эйлера: \(c^d \equiv (m^e)^d = m^{e d} \equiv m^{1 + k \varphi(n)} \equiv m \cdot (m^{\varphi(n)})^k \equiv m \pmod{n}\), так как \(m^{\varphi(n)} \equiv 1 \pmod{n}\).

Проверка простоты чисел

Теорема Эйлера лежит в основе некоторых вероятностных тестов простоты, таких как тест Ферма. Если для числа \(n\) существует такое \(a\), взаимно простое с \(n\), что \(a^{n-1} \not\equiv 1 \pmod{n}\), то \(n\) — составное. Однако существуют составные числа (числа Кармайкла), для которых это сравнение выполняется для всех \(a\), взаимно простых с \(n\), что делает тест Ферма несовершенным.

Вычисление обратных элементов

Теорема Эйлера даёт способ нахождения мультипликативного обратного элемента \(a^{-1} \mod n\): если \(\gcd(a, n) = 1\), то \(a^{-1} \equiv a^{\varphi(n)-1} \pmod{n}\). На практике для больших \(n\) это менее эффективно, чем расширенный алгоритм Евклида.

Примеры

1. Модуль \(n = 10\): \(\varphi(10) = 4\). Для \(a = 3\): \(3^4 = 81 \equiv 1 \pmod{10}\). Для \(a = 7\): \(7^4 = 2401 \equiv 1 \pmod{10}\).
2. Модуль \(n = 12\): \(\varphi(12) = 4\). Для \(a = 5\): \(5^4 = 625 \equiv 1 \pmod{12}\) (так как \(12 \cdot 52 = 624\)). Для \(a = 7\): \(7^4 = 2401 \equiv 1 \pmod{12}\) (\(12 \cdot 200 = 2400\)).
3. Модуль \(n = 15\): \(\varphi(15) = 8\). Для \(a = 2\): \(2^8 = 256 \equiv 1 \pmod{15}\) (\(15 \cdot 17 = 255\)). Для \(a = 4\): \(4^8 = 65536 \equiv 1 \pmod{15}\) (так как \(4^2 = 16 \equiv 1 \pmod{15}\), следовательно \(4^8 = (4^2)^4 \equiv 1\)).

Критика и ограничения

Теорема Эйлера является необходимым, но не достаточным условием для существования первообразных корней. Она не даёт способа эффективного вычисления \(\varphi(n)\) для больших \(n\) без знания разложения на простые множители, что является основой стойкости RSA. Кроме того, теорема неприменима, если \(a\) и \(n\) не являются взаимно простыми; в таких случаях используется обобщение — теорема Эйлера для составных модулей с учётом делимости.

Источники

• Эйлер Л. «Theoremata arithmetica nova methodo demonstrata» (1736).
• Виноградов И. М. «Основы теории чисел». — М.: Наука, 1972.
• Бухштаб А. А. «Теория чисел». — М.: Просвещение, 1966.
• Ривест Р., Шамир А., Адлеман Л. «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems» (1978).
• Кармайкл Р. Д. «On the numerical factors of the arithmetic forms \(\alpha^n \pm \beta^n\)» (1912).