Что такое функция Эйлера?
Функция Эйлера, которую обозначают \(\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)\). Именно поэтому и работает формула произведения по различным простым множителям.
