Функция Эйлера φ(n)

Исходное n	36
Простых множителей	2

Что показывает функция Эйлера φ(n)

Круг точек и шестерёнок с выделенными взаимно простыми позициями

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

Для вычисления достаточно найти различные простые делители n и применить формулу произведения:

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

Буква p пробегает только различные простые делители. Показатель степени не создаёт новый множитель. Для 36 = 2² × 3² получаем 36 × (1 - 1/2) × (1 - 1/3) = 12. Калькулятор выполняет те же действия в целых числах: сначала делит текущий результат на p, затем умножает на p - 1.

NIST Digital Library of Mathematical Functions, раздел 27.2 определяет φ(n) как количество положительных m ≤ n, взаимно простых с n. Там же приведена контрольная таблица: для 36 значение φ равно 12. По соглашению φ(1) = 1, хотя у единицы нет простых делителей.

Почему в формуле учитываются только разные простые делители

Возьмём числа от 1 до n. Если простое p делит n, все кратные p не могут быть взаимно простыми с n. Доля таких чисел равна 1/p, значит, после исключения остаётся доля 1 - 1/p. Для нескольких разных простых делителей эти доли перемножаются.

У числа 12 простые делители 2 и 3. Сначала из двенадцати кандидатов исключается половина, кратная 2: остаётся 6. Затем учитывается делитель 3: 6 ÷ 3 × 2 = 4. Повторно применять двойку не нужно, хотя в разложении 12 = 2² × 3 она встречается во второй степени. Все кратные 2 уже были исключены первым шагом.

Алгоритм делит остаток на найденный простой множитель до тех пор, пока тот не исчезнет. Кандидаты проверяются, пока p не станет больше остатка, делённого на p. Если после цикла остаток больше 1, он сам является последним простым множителем. При верхней границе 10¹² достаточно проверить кандидатов не выше 10⁶.

Примеры функции Эйлера

🔸 Единица. По определению φ(1) = 1. В интервале от 1 до 1 рассматривается только число 1, а gcd(1, 1) равен 1. В формуле простых множителей нет, поэтому работает пустое произведение.

💎 Простое число 97. Все положительные числа от 1 до 96 взаимно просты с 97, а само 97 имеет общий делитель 97. Поэтому φ(97) = 96. Если нужно отдельно подтвердить простоту аргумента, используйте проверку простого числа.

◻️ Квадрат 9. Разложение равно 3². Вычисление даёт 9 ÷ 3 × 2 = 6. Подходящие числа: 1, 2, 4, 5, 7 и 8. Степень двойки в записи отсутствует, поэтому применяется только один простой множитель 3.

🧩 Число 12. Простые делители равны 2 и 3. Получаем 12 ÷ 2 × 1 = 6, затем 6 ÷ 3 × 2 = 4. Результат подтверждает прямой список 1, 5, 7 и 11.

⚙️ Число 36. Разложение 2² × 3² содержит два различных простых делителя. Формула даёт 36 ÷ 2 × 1 = 18 и 18 ÷ 3 × 2 = 12. Повторные степени не меняют набор исключаемых кратных.

📦 Число 100. Простая факторизация равна 2² × 5². Получаем 100 ÷ 2 × 1 = 50, затем 50 ÷ 5 × 4 = 40. Значит, среди ста положительных чисел ровно сорок не имеют с сотней общего делителя больше единицы.

Как интерпретировать результат

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

Например, φ(40) = 16, потому что 40 = 2³ × 5. Доля взаимно простых чисел равна (1 - 1/2) × (1 - 1/5) = 2/5. У 97 доля равна 96/97, почти все меньшие числа подходят. Сравнение φ(n) / n помогает увидеть, насколько плотно число связано с малыми простыми множителями.

Функция используется в модульной арифметике. Теорема Эйлера утверждает: если a и n взаимно просты, то a^φ(n) даёт остаток 1 при делении на n. Например, φ(10) = 4, поэтому для a = 3 получаем 3⁴ = 81, а остаток от деления 81 на 10 равен 1. Это свойство встречается в теории чисел и криптографических построениях.

Функция Эйлера тесно связана с делителями, но не равна их количеству. Для 36 значение φ равно 12, а число положительных делителей равно 9. Полный список, τ(n) и σ(n) показывает калькулятор делителей числа. Смешивать эти функции нельзя: они отвечают на разные вопросы.

Точность, границы и ошибки ввода

Расчёт выполняется целыми числами произвольной длины. Промежуточная операция result ÷ p всегда даёт целое число, потому что p является простым делителем исходного n и соответствующие множители формулы можно применять последовательно. Округление и числа с плавающей запятой не нужны.

Допустимый диапазон составляет от 1 до 1 000 000 000 000. Ноль исключён: стандартная функция Эйлера определяется для положительного целого аргумента. Дробное число тоже не подходит, а отрицательный знак форма не принимает. Если ввод пуст, вычисление останавливается и вместо старого ответа появляется понятная подсказка.

На больших простых числах близко к верхней границе пробное деление требует больше шагов, чем на чётных или легко раскладывающихся значениях. Ограничение в 10¹² удерживает максимальный перебор в пределах миллиона кандидатов и при этом покрывает учебные, программные и большинство ручных проверок.

Вопросы о функции Эйлера

Ответы уточняют особые значения, роль простых множителей и связь φ(n) с взаимной простотой и модульной арифметикой.

Почему φ(1) равно 1?

Таково стандартное определение функции. В диапазоне 1 ≤ m ≤ 1 находится только m = 1, а наибольший общий делитель gcd(1, 1) равен 1.

Чему равна функция Эйлера для простого числа p?

φ(p) = p - 1. Все числа от 1 до p - 1 взаимно просты с p, а само p имеет с собой общий делитель p.

Почему степень простого множителя не повторяет шаг формулы?

Множитель 1 - 1/p исключает все числа, кратные p, сразу. Повторная степень p не создаёт новую группу чисел с другим общим простым делителем.

Может ли φ(n) быть нечётным?

Для n > 2 значение φ(n) всегда чётно. Взаимно простые остатки можно объединить в пары a и n - a. Нечётное значение 1 получается только для n = 1 и n = 2.

Чем φ(n) отличается от количества делителей τ(n)?

φ(n) считает положительные числа до n, взаимно простые с ним. τ(n) считает сами положительные делители n. Для 36 эти значения равны 12 и 9 соответственно.

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

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

Где применяется функция Эйлера?

Она используется в теории сравнений, теореме Эйлера, построении приведённых систем вычетов и некоторых криптографических алгоритмах.

Определена ли φ(n) для нуля и дробей?

В этом стандартном арифметическом определении аргумент является положительным целым числом. Поэтому калькулятор принимает значения от 1 и отклоняет ноль и дроби.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.