Математика · объяснение и практика

Функция Эйлера: сколько чисел до 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. Поэтому значение функции в этих случаях чётное.

От чтения к действию

А теперь — вы

Чему равно φ(28)?

Частые вопросы

Функция Эйлера считает простые числа до n?

Нет. Она считает числа, взаимно простые с n; многие из них могут быть составными.

Почему повторный простой делитель не добавляет второй множитель?

Все кратные его более высокой степени уже входят в класс кратных самому простому. Повторное исключение изменило бы правильный подсчёт.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться