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

Теория

Функция Эйлера \(\varphi(n)\) считает, сколько натуральных чисел от 1 до \(n\) взаимно просты с \(n\), то есть не имеют с ним общих делителей, кроме единицы. Например, среди чисел от 1 до 12 взаимно просты с 12 только 1, 5, 7 и 11 — значит, \(\varphi(12) = 4\).

Формула через разложение на простые: если \(n = p_1^{k_1} \times p_2^{k_2} \times \ldots\), то \(\varphi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots\). Для простого \(p\) получается \(\varphi(p) = p - 1\). Функция Эйлера лежит в основе теоремы Эйлера и криптографии RSA.

Важно: число 1 взаимно просто с любым числом и всегда учитывается; у простых \(p\) значение равно \(p-1\).

Пример с решением

1. Условие. Найдите \(\varphi(12)\).
2. Формула. \(\varphi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right)\).
3. Подстановка. \(12 = 2^2 \times 3\), значит, \(\varphi(12) = 12 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right)\).
4. Вычисление. \(12 \times \frac{1}{2} \times \frac{2}{3} = 4\).
5. Ответ. \(\varphi(12) = 4\) — числа 1, 5, 7, 11. Калькулятор с полем 12 покажет то же значение.

Главное

• \(\varphi(n)\) — количество чисел от 1 до \(n\), взаимно простых с \(n\).
• Формула: \(\varphi(n) = n \times \prod\left(1 - \frac{1}{p_i}\right)\) по простым делителям.
• Для простого p: \(\varphi(p) = p - 1\).