Математика · объяснение и практика
Функция Эйлера: сколько чисел до n взаимно просты с n
Считаем взаимно простые остатки через простые делители числа, учитываем повторные степени и отличаем функцию Эйлера от количества простых чисел.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Функция φ(n) считает положительные целые не больше n, взаимно простые с n. Если известны различные простые делители p числа n, то φ(n) = n·∏(1−1/p). Каждый различный простой учитывается один раз независимо от его степени.
Какие числа попадают в подсчёт
Для n = 36 допустимы 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 и 35. Их двенадцать. Среди них есть составные 25 и 35, поэтому функция не считает только простые числа. Условие состоит в отсутствии общего делителя с тридцатью шестью, а не в собственной простоте проверяемого остатка.
Число один включается, поскольку взаимно просто с любым натуральным n. Само n при n > 1 не включается, ведь НОД(n,n) = n. В принятом положительном определении φ(1) = 1. Явное уточнение границ помогает не спутать подсчёт взаимно простых представителей с количеством всех ненулевых остатков или с длиной какого-либо периода степени.
Как исключить запрещённые простые делители
У числа 36 простые делители два и три. Из 36 представителей убираем 18 чётных и 12 кратных трём, но шесть кратных шести были вычеркнуты дважды и должны быть возвращены один раз. Получаем 36−18−12+6 = 12. В произведении тот же результат записывается 36·(1−1/2)·(1−1/3).
Повторная степень простого не создаёт нового вида запрещённых чисел. Делимость на четыре уже подразумевает делимость на два, поэтому второй одинаковый множитель (1−1/2) добавлять нельзя. Для 45 = 3²·5 формула даёт 45·(1−1/3)·(1−1/5) = 24. Квадрат тройки сохраняется в самом n, но тройка как различный простой делитель встречается в произведении один раз.
Пример
Найдите φ(20), используя простые делители.
Число 20 имеет различные простые делители 2 и 5. Поэтому φ(20) = 20·(1/2)·(4/5) = 8. Представители 1, 3, 7, 9, 11, 13, 17 и 19 подтверждают подсчёт.
Когда можно перемножать значения функции
Если m и n взаимно просты, выполняется φ(mn) = φ(m)φ(n). Без взаимной простоты это правило нельзя применять автоматически. Например, φ(2) = 1 и φ(4) = 2, но φ(8) = 4, а не два. Общая простая часть меняет структуру исключаемых остатков, поэтому обычное произведение двух отдельных подсчётов не соответствует новой задаче.
Для простого p все положительные представители от одного до p−1 взаимно просты с ним, значит, φ(p) = p−1. Для степени pᵏ остаётся pᵏ−pᵏ⁻¹. Эти частные формулы удобно проверять прямым подсчётом небольших чисел, но общий метод требует корректного разложения n на различные простые делители. Неверное разложение переносится в ответ даже при безошибочном умножении дробей. Дополнительная проверка при n > 2: допустимые представители разбиваются на разные пары k и n−k. Оба имеют один НОД с n, а середина n/2 не может быть взаимно простой при n > 2. Поэтому значение функции в этих случаях чётное.
От чтения к действию
А теперь — вы
Частые вопросы
Функция Эйлера считает простые числа до n?
Нет. Она считает числа, взаимно простые с n; многие из них могут быть составными.
Почему повторный простой делитель не добавляет второй множитель?
Все кратные его более высокой степени уже входят в класс кратных самому простому. Повторное исключение изменило бы правильный подсчёт.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как уменьшать показатель степени по теореме Эйлера
Сокращаем показатель степени при составном модуле через функцию Эйлера, проверяем взаимную простоту и отличаем гарантированный период от наименьшего.
Открыть темуОбратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.
Открыть тему