Функция Эйлера простыми словами

Выпишите числа от 1 до 10 и вычеркните каждое, у которого есть общий делитель с 10. Останутся четыре: 1, 3, 7 и 9. Это количество, φ(10) = 4, и есть функция Эйлера, одна из самых используемых функций теории чисел — от дробей и часов до шифрования, которое защищает платежи в интернете.

Числа от 1 до 30 в сетке, восемь взаимно простых с 30 закрашены, формула φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 и график φ(k), на котором простые числа лежат на прямой
Числа от 1 до 30 в сетке, восемь взаимно простых с 30 закрашены, формула φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 и график φ(k), на котором простые числа лежат на прямой

Подсчёт взаимно простых чисел

Два числа взаимно просты, когда их наибольший общий делитель равен 1. φ(n) считает k от 1 до n с НОД(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 и φ(1) = 1. То же самое количество встречается во многих местах. Это число дробей k/n между 0 и 1, которые уже несократимы, число длин шагов, при которых стрелка часов с n делениями проходит через каждое деление, и число таких k, у которых есть обратный элемент по модулю n, так что уравнение k × x ≡ 1 (mod n) имеет решение.

Формула произведения

Если n делится на простые числа p₁, p₂ …, то φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Причина — решето. Половина всех чисел чётна, поэтому после удаления кратных 2 остаётся доля 1 − 1/2; среди оставшихся каждое третье кратно 3, и так далее. По китайской теореме об остатках условия для разных простых независимы, поэтому доли просто перемножаются. Для 100 = 2² × 5² получается 100 × 1/2 × 4/5 = 40. Два свойства дают тот же результат в другой форме: φ(p^k) = p^(k−1)(p − 1) и φ(mn) = φ(m) φ(n) для взаимно простых m и n, так что φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

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

Ферма заметил в 1640 году, что a^(p−1) ≡ 1 (mod p) для простого p и любого a, не делящегося на p. Эйлер доказал общий вариант, опубликованный в 1763 году: a^φ(n) ≡ 1 (mod n) всякий раз, когда НОД(a, n) = 1. Доказательство короткое. Умножьте на a все φ(n) чисел, взаимно простых с n; произведения снова взаимно просты с n и попарно различны по модулю n, то есть это те же числа в другом порядке, и сравнение двух произведений оставляет a^φ(n) ≡ 1. Наименьший показатель, подходящий для данного a, — его порядок, который всегда делит φ(n); наименьший, подходящий сразу для всех a, — функция Кармайкла λ(n). Для 561 = 3 × 11 × 17 число λ(561) = 80 делит 560, поэтому a^560 ≡ 1 (mod 561) для каждого a, взаимно простого с 561, хотя 561 не простое. Это наименьшее число Кармайкла и причина, по которой один только тест Ферма не может доказать, что число простое.

Леонард Эйлер на портрете Якоба Эмануэля Хандманна. В 1763 году он опубликовал общий вид наблюдения Ферма: a^φ(n) ≡ 1 (mod n), когда a и n взаимно просты.
Леонард Эйлер на портрете Якоба Эмануэля Хандманна. В 1763 году он опубликовал общий вид наблюдения Ферма: a^φ(n) ≡ 1 (mod n), когда a и n взаимно просты.

Сумма Гаусса по делителям и среднее значение

Сложите φ(d) по всем делителям d числа n, и всегда снова получится n: для 12 φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Гаусс доказал это в своих «Арифметических исследованиях» 1801 года; это видно, если сократить дроби 1/12, 2/12 … 12/12 и рассортировать их по знаменателям. В среднем φ(k) составляет около 0,61 k: среднее φ(k)/k стремится к 6/π² ≈ 0,6079, и это же вероятность того, что два случайных целых числа взаимно просты, а φ(1) + … + φ(N) близко к 3N²/π². Для N = 1 000 сумма равна 304 192 против 3N²/π² ≈ 303 964.

Карл Фридрих Гаусс на портрете Кристиана Альбрехта Йенсена 1840 года. Обозначение сравнения a ≡ b (mod n) он ввёл в Disquisitiones Arithmeticae 1801 года.
Карл Фридрих Гаусс на портрете Кристиана Альбрехта Йенсена 1840 года. Обозначение сравнения a ≡ b (mod n) он ввёл в Disquisitiones Arithmeticae 1801 года.

Значения, которые никогда не встречаются

φ(n) чётно для каждого n начиная с 3, потому что числа, взаимно простые с n, идут парами k и n − k. Но и не каждое чётное число бывает значением: 14, 26, 34, 38 и 50 — первые, которые никогда не встречаются, а 24 — значение для десяти разных чисел, от 35 до 90. Найти их — конечный перебор, потому что для каждого простого p, делящего n, число p − 1 должно делить φ(n). В 1907 году Роберт Кармайкл утверждал, что никакое значение не принимается ровно один раз. Его доказательство было ошибочным, вопрос до сих пор открыт, а любое исключение должно быть больше 10^(10^10). Д. Г. Лемер спросил в 1932 году, может ли φ(n) делить n − 1 для составного n; ни одного примера не известно.

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

RSA выбирает два больших простых числа p и q и публикует n = pq и показатель e. Поскольку φ(n) = (p − 1)(q − 1), тот, кто умеет разложить n, может вычислить φ(n), а из неё — закрытый показатель d с e × d ≡ 1 (mod φ(n)); теорема Эйлера тогда гарантирует, что (m^e)^d ≡ m (mod n). В учебном примере n = 3233 = 61 × 53 имеем φ(n) = 3 120, e = 17 и d = 2 753. Многие реализации используют вместо этого λ(n) = НОК(p − 1, q − 1), здесь 780, что даёт меньшее d = 413. Вычислить φ(n) для модуля RSA из 600 цифр так же трудно, как разложить его: по n и φ(n) оба простых числа находятся с помощью одного квадратного корня.

Рон Ривест, Ади Шамир и Лен Адлеман (слева направо)
Рон Ривест, Ади Шамир и Лен Адлеман (слева направо)

Попробуйте сами

Откройте калькулятор и введите любое n до 10^18, чтобы увидеть φ(n) с простыми делителями и формулой. До 500 числа от 1 до n рисуются: взаимно простые закрашены, остальные окрашены по наименьшему простому, общему у них с n, так что формула произведения превращается в решето, которое можно пересчитать. Выберите число a, чтобы проверить теорему Эйлера, переключитесь на «График», чтобы увидеть φ(k) до 100 000 с простыми числами на прямой φ(p) = p − 1, или на «Обращение», чтобы найти все n с φ(n) = m.

Часто задаваемые вопросы

Почему φ(1) = 1?

Потому что НОД(1, 1) = 1: единственное число от 1 до 1 взаимно просто с 1. Это соглашение также сохраняет формулы верными, например сумму Гаусса по делителям n, которая при n = 1 есть просто φ(1) = 1.

Совпадает ли φ с функцией распределения простых чисел?

Нет. π(n) считает простые числа до n, а φ(n) — числа до n, взаимно простые с n. φ(10) = 4 считает 1, 3, 7 и 9, а π(10) = 4 считает 2, 3, 5 и 7. Здесь они совпадают случайно: φ(12) = 4, но π(12) = 5.

Как быстро можно вычислить φ(n)?

Так же быстро, как можно разложить n. Если простые делители известны, нужно лишь несколько умножений; без них быстрый способ неизвестен, и именно на этом держится RSA. Для чисел до 10^18 разложение в браузере занимает миллисекунды, для чисел из сотен цифр оно может занять годы.

У каких чисел φ(n) наименьшая по сравнению с n?

У чисел со многими маленькими простыми делителями. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… зависит только от того, какие простые делят n, а не от их степеней: для любой степени 2 это ровно 1/2, а для 30 = 2 × 3 × 5 это 8/30, около 27 %. У произведения первых 15 простых чисел, 614 889 782 588 491 410, φ(n)/n ≈ 14 % — наименьшее значение среди всех чисел до 10^18.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть калькулятор