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

Функция Эйлера (также известная как φ-функция Эйлера или тотиент-функция) — это мультипликативная арифметическая функция, которая для натурального числа \( n \) определяет количество целых чисел от 1 до \( n \), взаимно простых с \( n \). Иными словами, \(\varphi(n)\) равна мощности множества чисел \( k \) (где \( 1 \le k \le n \)), для которых наибольший общий делитель (НОД) \( \gcd(k, n) = 1 \). Функция названа в честь швейцарского математика Леонарда Эйлера, который ввёл её в 1763 году в работе «Theoremata arithmetica nova methodo demonstrata» и систематически использовал в теории чисел. Функция Эйлера является одной из фундаментальных функций в элементарной и аналитической теории чисел, играя ключевую роль в формулировке и доказательстве малой теоремы Ферма, теоремы Эйлера, а также в криптографии (в частности, в алгоритме RSA).

Определение и основные свойства

Формально функция Эйлера \(\varphi: \mathbb{N} \to \mathbb{N}\) определяется как: \[ \varphi(n) = \#\{ k \in \mathbb{N} \mid 1 \le k \le n, \ \gcd(k, n) = 1 \}. \] По определению, \(\varphi(1) = 1\), так как число 1 взаимно просто с самим собой.

Мультипликативность

Функция Эйлера является мультипликативной: для любых взаимно простых натуральных чисел \( m \) и \( n \) (то есть \(\gcd(m, n) = 1\)) выполняется равенство: \[ \varphi(mn) = \varphi(m) \cdot \varphi(n). \] Это свойство позволяет вычислять \(\varphi(n)\) через разложение числа на простые множители.

Формула для вычисления

Если каноническое разложение числа \( n \) на простые множители имеет вид: \[ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}, \] где \( p_1, p_2, \ldots, p_k \) — различные простые числа, а \( e_1, e_2, \ldots, e_k \) — их положительные степени, то: \[ \varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right). \] Эта формула следует из принципа включения-исключения. Например, для простого числа \( p \): \[ \varphi(p) = p - 1, \] так как все числа от 1 до \( p-1 \) взаимно просты с \( p \). Для степени простого числа \( p^e \): \[ \varphi(p^e) = p^e - p^{e-1} = p^{e-1} (p - 1). \]

Примеры

• \(\varphi(1) = 1\).
• \(\varphi(2) = 1\) (число 1 взаимно просто с 2).
• \(\varphi(6) = 2\) (числа 1 и 5 взаимно просты с 6).
• \(\varphi(12) = 4\) (числа 1, 5, 7, 11).

История

Леонард Эйлер впервые опубликовал понятие тотиент-функции в 1763 году в статье «Theoremata arithmetica nova methodo demonstrata» (Новые теоремы арифметики, доказанные новым методом). Однако сам термин «функция Эйлера» и обозначение \(\varphi(n)\) ввёл в 1801 году Карл Фридрих Гаусс в своём труде «Disquisitiones Arithmeticae». Гаусс использовал эту функцию для изучения свойств квадратичных вычетов и циклических групп. В XIX веке функция Эйлера стала центральным объектом исследований в работах Адриена-Мари Лежандра, Петера Густава Лежёна Дирихле, Бернхарда Римана и других математиков, что привело к развитию аналитической теории чисел.

Классификация и связанные понятия

Обобщения

Существует несколько обобщений функции Эйлера:

• Функция Иордана \( J_k(n) \) — обобщение, считающее количество \( k \)-кортежей целых чисел, взаимно простых с \( n \).
• Функция Кармайкла \( \lambda(n) \) — наименьшее положительное число \( m \), такое что для любого \( a \), взаимно простого с \( n \), выполняется \( a^m \equiv 1 \pmod{n} \). Для многих \( n \) \(\lambda(n)\) является делителем \(\varphi(n)\).

Связь с другими функциями

Функция Эйлера тесно связана с:

• Функцией Мёбиуса \( \mu(n) \): \(\varphi(n) = \sum_{d \mid n} \mu(d) \cdot \frac{n}{d}\).
• Суммой делителей \( \sigma(n) \): \(\sum_{d \mid n} \varphi(d) = n\).
• Функцией Чебышёва и распределением простых чисел.

Теоремы, связанные с функцией Эйлера

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

Для любых взаимно простых целых чисел \( a \) и \( n \) (где \( n > 0 \)) выполняется: \[ a^{\varphi(n)} \equiv 1 \pmod{n}. \] Эта теорема является обобщением малой теоремы Ферма (которая справедлива только для простых \( n \)) и лежит в основе алгоритма RSA.

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

Как частный случай теоремы Эйлера: если \( p \) — простое число, то для любого целого \( a \), не делящегося на \( p \): \[ a^{p-1} \equiv 1 \pmod{p}. \]

Формула Гаусса

Для любого натурального \( n \): \[ \sum_{d \mid n} \varphi(d) = n. \] Эта формула выражает тот факт, что сумма значений функции Эйлера по всем делителям числа \( n \) равна самому \( n \). Она имеет важное значение в комбинаторике и теории групп.

Применение

Криптография

Функция Эйлера является ключевым элементом в криптосистеме RSA (Rivest–Shamir–Adleman). В RSA выбираются два больших простых числа \( p \) и \( q \), вычисляется \( n = p \cdot q \) и \(\varphi(n) = (p-1)(q-1)\). Открытый и закрытый ключи строятся на основе модуля \( n \) и значения \(\varphi(n)\). Стойкость RSA основана на сложности факторизации больших чисел, что эквивалентно сложности вычисления \(\varphi(n)\) без знания разложения.

Теория чисел

Функция Эйлера используется в:

• Исследовании распределения простых чисел (например, в формуле для суммы обратных значений простых чисел).
• Доказательстве бесконечности простых чисел в арифметических прогрессиях (теорема Дирихле).
• Построении циклических групп (группа \( (\mathbb{Z}/n\mathbb{Z})^\times \) имеет порядок \(\varphi(n)\)).

Комбинаторика и алгебра

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

Асимптотика и распределение

Среднее значение функции Эйлера ведёт себя как: \[ \frac{1}{n} \sum_{k=1}^n \varphi(k) \sim \frac{3}{\pi^2} n \approx 0.30396 \cdot n. \] Эта асимптотика была доказана Францем Мертенсом в 1874 году. Для отдельных значений \(\varphi(n)\) справедлива оценка: \[ \varphi(n) \ge \sqrt{\frac{n}{2}} \quad \text{для всех } n \ge 2, \] а также более точная оценка: \[ \varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}, \] где \(\gamma\) — постоянная Эйлера—Маскерони (для достаточно больших \( n \)).

Интересные факты

• Значение \(\varphi(n)\) всегда чётно для \( n > 2 \), так как если \( a \) взаимно просто с \( n \), то и \( n-a \) взаимно просто с \( n \), и \( a \neq n-a \) при \( n > 2 \).
• Функция Эйлера не является инъективной: например, \(\varphi(3) = \varphi(4) = 2\).
• Рекордные значения \(\varphi(n)\) для больших \( n \) используются в задачах теории чисел и криптографии.
• В 1909 году Эдмунд Ландау доказал, что для любого \( k > 1 \) существует бесконечно много \( n \), таких что \(\varphi(n) = k\).

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

Несмотря на широкое применение, функция Эйлера имеет ряд ограничений:

• Её вычисление для больших чисел требует знания разложения на простые множители, что является вычислительно сложной задачей (предположительно, не принадлежащей классу P).
• Функция не является мультипликативной для произвольных пар чисел (только для взаимно простых), что усложняет её использование в некоторых комбинаторных задачах.
• В криптографии уязвимость RSA связана не с самой функцией, а с возможностью факторизации \( n \); однако при неудачном выборе параметров (например, слишком маленьких простых чисел) \(\varphi(n)\) может быть вычислена тривиально.

Источники

• Эйлер Л. «Theoremata arithmetica nova methodo demonstrata» (1763).
• Гаусс К. Ф. «Disquisitiones Arithmeticae» (1801).
• Харди Г. Х., Райт Э. М. «Введение в теорию чисел» (глава 5).
• Айерлэнд К., Роузен М. «Классическое введение в современную теорию чисел».
• Боревич З. И., Шафаревич И. Р. «Теория чисел».
• Rivest R., Shamir A., Adleman L. «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems» (1978).