Что такое функция Эйлера?
Функция Эйлера, которую обозначают \(\varphi(n)\), показывает, сколько натуральных чисел в диапазоне от 1 до n не имеют с n общих делителей, кроме единицы, — то есть являются взаимно простыми с n. Например, \(\varphi(9) = 6\), потому что числа 1, 2, 4, 5, 7 и 8 взаимно просты с девяткой. Эта функция — одно из ключевых понятий теории чисел, и она широко применяется в криптографии. Самый известный пример — алгоритм RSA, где значение \(\varphi(n)\) определяет обратный элемент по модулю, используемый при генерации ключей.
Как пользоваться калькулятором
Введите любое натуральное число n и нажмите «Вычислить». Калькулятор разложит n на различные простые множители, применит формулу произведения и мгновенно выдаст значение \(\varphi(n)\), а заодно покажет список найденных простых делителей. Инструмент одинаково хорошо справляется как с небольшими числами, так и с очень большими — вплоть до миллиарда.
Разбираем формулу
Самый эффективный способ вычислить функцию Эйлера — формула произведения:
$$\varphi\!\left(n\right) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$, где произведение берётся по всем различным простым числам p, на которые делится n.
Важны именно различные простые множители, а не их кратности. Каждый сомножитель \(\left(1 - \frac{1}{p}\right)\) «отсекает» долю чисел, которые делятся на это простое число.
Пример с решением
Возьмём n = 36. Его разложение на простые множители — \(2^2 \times 3^2\), то есть различные простые числа здесь 2 и 3. Тогда:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}.$$
Значит, ровно 12 целых чисел от 1 до 36 взаимно просты с 36.
Частые вопросы
Чему равно \(\varphi(1)\)? По соглашению \(\varphi(1) = 1\), поскольку единица взаимно проста сама с собой.
Чему равно φ от простого числа p? Для любого простого p выполняется \(\varphi(p) = p - 1\), ведь каждое число от 1 до p−1 взаимно просто с p.
Мультипликативна ли функция Эйлера? Да. Если \(\gcd(a, b) = 1\), то \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\). Именно поэтому и работает формула произведения по различным простым множителям.
Ещё примеры вычислений
Пример 1: простое число, φ(13)
13 — простое число, поэтому его единственный простой делитель — это само 13:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Это совпадает с простым правилом \(\varphi(p) = p-1\).
Пример 2: степень простого числа, φ(32)
Разложение: \(32 = 2^5\). Единственное различное простое число здесь — 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
Эквивалентная форма для степени простого числа: \(\varphi(p^k) = p^k - p^{k-1}\), поэтому \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Это в точности нечётные числа от 1 до 31.
Пример 3: три или более различных простых числа, φ(210)
Разложение: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- Начинаем с \(210\).
- Умножаем на \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
- Умножаем на \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
- Умножаем на \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
- Умножаем на \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).
Итак, \(\varphi(210) = \)48. Обратите внимание, что правило произведения использует каждое различное простое число только один раз. Например, \(60 = 2^2 \cdot 3 \cdot 5\) даёт \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
Интерпретация φ(n) и её применения
- Связь с простотой: для \(n \ge 2\) равенство \(\varphi(n) = n-1\) выполняется тогда и только тогда, когда \(n\) простое. Каждое число, меньшее простого, взаимно просто с ним. Если \(n\) составное, хотя бы одно меньшее число имеет с ним общий делитель, поэтому \(\varphi(n) < n-1\).
- Группа обратимых элементов: \(\varphi(n)\) — это количество элементов в группе обратимых элементов по модулю \(n\), то есть вычетов, имеющих мультипликативный обратный по модулю \(n\). Для \(n = 15\) это 1, 2, 4, 7, 8, 11, 13, 14, что даёт 8 элементов.
- Теорема Эйлера: если \(\gcd(a, n) = 1\), то \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Пример: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, и \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Малая теорема Ферма — частный случай при \(n = p\), где \(p\) простое.
- RSA: если \(n = pq\) для различных простых \(p\) и \(q\), то \(\varphi(n) = (p-1)(q-1)\). При \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). Открытый показатель \(e\) должен быть взаимно прост с \(\varphi(n)\), а закрытый показатель \(d\) удовлетворяет \(ed \equiv 1 \pmod{\varphi(n)}\). В настоящем RSA используются простые числа длиной в сотни цифр. Тот, кто может разложить \(n\) на множители, может вычислить \(\varphi(n)\), поэтому безопасность опирается на то, что факторизация трудна.
- Отношение зависит только от различных простых делителей: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Показатели степеней не важны. Например, у 6 и 12 одно и то же множество простых делителей {2, 3}, поэтому \(\varphi(6)/6 = 2/6 = 1/3\) и \(\varphi(12)/12 = 4/12 = 1/3\).