Математика / Арифметика и теория чисел

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

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)

Схема Взаимная простота с числом 12

Четыре числа имеют НОД с 12, равный единице.

Обозначения

$φ(n)$: число положительных целых ≤n, взаимно простых с n, безразмерная величина
$n$: положительное целое число, безразмерная величина
$p$: различный простой делитель n, безразмерная величина

Условия применения

Число n положительное целое. Произведение берут по различным простым p, делящим n, без повторения одного p для каждой его степени. При n=1 произведение пустое и равно единице, так что φ(1)=1 по стандартному соглашению.

Ограничения

Формула не находит простое разложение автоматически: для большого n именно факторизация может быть трудной частью. Нельзя перемножать φ двух произвольных чисел без условия их взаимной простоты. Результат считает взаимно простые числа, а не простые числа в диапазоне.

Подробное объяснение

Чтобы число было взаимно просто с n, оно не должно делиться ни на один простой делитель n. Поэтому задача сводится к исключению кратных простым из диапазона от 1 до n. Степень простого в n не создаёт нового запрета: кратность p уже исключает кратность p².

Если n является степенью p, среди n чисел ровно n/p кратны p. Остаётся n−n/p=n(1−1/p). Для нескольких различных простых одновременные кратности учитываются включением–исключением; раскрытие произведения даёт те же поправки к пересечениям.

Например, для n=12 запреты связаны только с 2 и 3. Удаление кратных двойке и тройке оставляет 1,5,7,11. Произведение 12·(1−1/2)·(1−1/3)=4 сразу воспроизводит этот результат, не проверяя НОД каждого числа по отдельности.

При простом n=p все числа 1,…,p−1 взаимно просты с ним, поэтому φ(p)=p−1. Для составного n значение обычно меньше. Однако функция не возрастает строго с n: новое число может иметь больше различных простых делителей и исключать большую долю остатков.

Смысл результата полезен в арифметике по модулю: именно остатки, взаимно простые с модулем, имеют мультипликативные обратные. Это связывает подсчёт φ с решением сравнений, но само значение φ не сообщает, какой обратный соответствует конкретному остатку.

Как пользоваться формулой

Разложите n на простые множители и выпишите каждый различный простой делитель только один раз.
Для каждого простого p составьте множитель (p−1)/p, не повторяя его из-за степени p в разложении.
Умножьте n на все поправки, сокращая дроби точно; итог должен быть целым неотрицательным числом.
Для малого n проверьте ответ перебором НОД чисел от 1 до n или принципом включения–исключения.

Историческая справка

Функция носит имя Леонарда Эйлера и относится к развитию теории чисел XVIII века. Она позволяет описывать множество чисел, взаимно простых с заданным модулем, и появляется в обобщении малой теоремы Ферма. История обозначения отличается от истории самой идеи: справка MacTutor по символам теории чисел отмечает разные записи, использовавшиеся Эйлером и последующими авторами. Поэтому современную букву φ не следует автоматически считать первоначальным обозначением. В современной теории функция рассматривается как мультипликативная арифметическая функция, а произведение по простым связывает её с единственностью факторизации. NIST DLMF приводит эту запись в разделе мультипликативных свойств. Здесь используется современная нотация и элементарный вывод через исключение кратных.

Историческая линия формулы

Имя Эйлера относится к арифметической функции и её роли в теории сравнений. Современная запись φ(n) и терминология закреплялись постепенно; формула произведения объясняется структурой простых делителей, а не эмпирическим подбором коэффициентов для отдельных чисел.

Пример

Для n = 180 разложение 180 = 2² · 3² · 5. Различные простые делители: 2, 3 и 5. Поэтому φ(180) = 180 · (1 − 1/2) · (1 − 1/3) · (1 − 1/5) = 180 · 1/2 · 2/3 · 4/5 = 48. Независимая проверка включением–исключением: 180 − 90 − 60 − 36+30+18+12 − 6 = 48. Значит, ровно 48 чисел от 1 до 180 взаимно просты с 180, единиц измерения нет. В вычислении важно, что 2² и 3² не дают повторных множителей: учитываются только различные простые. Перебор НОД подтверждает интерпретацию: число 1 взаимно просто, 2 нет, 7 взаимно просто, а 180 нет; итоговый подсчёт относится ко всему диапазону, а не к выборочной проверке.

Частая ошибка

Не учитывайте простой p несколько раз из-за степени в разложении. Не называйте φ(n) количеством простых чисел до n: например, 1 входит в подсчёт взаимной простоты. Не применяйте φ(ab)=φ(a)φ(b), если НОД(a,b)>1. Не округляйте промежуточные дроби, иначе можно потерять целочисленный результат.

Практика

Задачи с решением

Двенадцать

Условие. Вычислите φ(12) и перечислите подходящие числа.

Решение. 12=2²·3, поэтому φ(12)=12·(1/2)·(2/3)=4. Взаимно просты 1,5,7,11.

Ответ. 4

Степень простого

Условие. Найдите φ(49).

Решение. 49=7². Исключаются семь кратных семи: φ(49)=49·(1−1/7)=42.

Ответ. 42

Дополнительные источники

https://dlmf.nist.gov/27.3
https://mathshistory.st-andrews.ac.uk//Miller/mathsym/nth/

Связанные формулы

Математика

Наибольший общий делитель

$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$

Наибольший общий делитель двух чисел равен произведению общих простых множителей, взятых в меньших степенях, и показывает самую большую общую меру чисел.

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Число делителей по разложению на простые множители

$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$

Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.