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

Формулировка и ключевые понятия

Функция Эйлера - это функция, обозначаемая $\varphi(n)$, которая для положительного целого числа n даёт число целых чисел от 1 до n, взаимно простых с n.

Теорема Эйлера - если целые числа a и n такие, что $\gcd(a,n)=1$, то выполняется соотношение $a^{\varphi(n)}\equiv 1\pmod{n}$.

Эта формула обобщает маленькую теорему Ферма и является фундаментальным результатом в элементарной теории чисел. Для понимания её значения полезно рассматривать структуру множеств вычетаемых классов по модулю n и множество обратимых элементов по модулю n. Именно количество таких обратимых элементов и равно значению $\varphi(n)$, что делает функцию важной при работе с обратимостями и степенями по модулю.

Важные частные случаи и свойства функции Эйлера включают формулы для простых чисел и для степеней простых: например, при простом p справедливо $\varphi(p)=p-1,\ \text{если }p\text{ — простое}$, а для степеней простого числа есть выражение $\varphi(p^{k})=p^{k}-p^{k-1}=p^{k}\left(1-\dfrac{1}{p}\right)$.

Основные свойства функции Эйлера

Функция $\varphi(n)$ обладает свойством мультипликативности на взаимно простых аргументах: если два числа a и b взаимно просты, то $\varphi(ab)=\varphi(a)\varphi(b)\quad\text{если }\gcd(a,b)=1$. Это упрощает вычисление $\varphi(n)$ для составных чисел: достаточно разложить число на простые множители и применить соответствующую формулу.

С помощью разложения числа n по простым множителям можно записать общую формулу для $\varphi(n)$: $\varphi(n)=n\prod_{p\mid n}\left(1-\dfrac{1}{p}\right)$. Эта запись даёт эффективный способ вычисления функции Эйлера через простые делители числа n, что важно в практических задачах и в криптографии.

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

Доказательство теоремы (схема)

Одна из стандартных стратегий доказательства опирается на идею перестановки обратимых элементов при умножении на фиксированное a, взаимно простое с n. Если рассмотреть все элементы множества обратимых вычетов и умножить каждое на a, то в результате получается та же самая совокупность вычетов, возможно в другом порядке, что приводит к равенству произведений по модулю n и далее к выводам о степенной редукции. Формально это обосновано тем, что отображение x↦ax индуцирует биекцию множества обратимых классов.

Другой взгляд — алгебраический: в группе единиц по модулю n порядок группы равен $|\mathbb{Z}_n^{\times}|=\varphi(n)$, а по теории групп порядок любого элемента делит порядок группы. Следовательно, порядок элемента a делит $\varphi(n)$, что даёт соотношение $\operatorname{ord}_n(a)\mid \varphi(n)$ и в итоге приводит к выводу $a^{\varphi(n)}\equiv 1\pmod{n}$.

Этот алгебраический подход короче и нагляднее для тех, кто знаком с основами теории групп; комбинаторный же подход даёт конструктивное понимание механизма, почему произведение элементов сохраняется при домножении на взаимно простое число.

Частные случаи и связанные теоремы

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

Более тонкое улучшение — функция Кармайкла λ(n), для которой для всех a, взаимно простых с n, верно $a^{\lambda(n)}\equiv 1\pmod{n}$. Значение λ(n) обычно делит $\varphi(n)$ и в ряде случаев меньше, поэтому в применениях, где важен минимальный общий показатель, используют λ(n).

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

Примеры и применение на практике

Применения в задачах и в криптографии

Теорема Эйлера лежит в основе многих методов нахождения обратных по модулю и используется в алгоритмах шифрования с открытым ключом, где ключи строятся на основе свойств мультипликативных групп по модулю n. В частных реализациях, например в RSA, важны именно свойства функции Эйлера и её вычисление для большого числа n, представленного как произведение двух простых чисел.

Кроме того, теорема активно применяется при решении диофантовых уравнений с остатками, при исследовании циклов степеней по модулю и при сведении сложных степенных вычислений к более простым. Знание формул для $\varphi(n)$ и умение применять теорему Эйлера существенно упрощает решение многих олимпиадных задач и практических вычислительных задач.

Иллюстрация принципа показана на схеме ниже:{IMAGE_0}