Что считает φ(n)
Функция Эйлера φ(n) — сколько целых k в диапазоне 1…n имеют НОД(k, n) = 1. Раздел: теория чисел.
Это не проверка простоты n и не список делителей. Взаимная простота одной пары — другая страница. Обратный элемент — обратный по модулю.
φ(1) = 1 по соглашению: единственное число в отрезке — единица, и НОД(1, 1) = 1. Для простого p значение p − 1. Для 9 = 3² значение 9·(1 − 1/3) = 6: 1, 2, 4, 5, 7, 8.
Произведение по простым
φ(n) — сколько чисел от 1 до n взаимно просты с n
Если n = p₁ᵏ¹ … pₘᵏᵐ, то φ(n) = n (1 − 1/p₁) … (1 − 1/pₘ). Каждый простой учитывают один раз, степень входит в n. Калькулятор раскладывает n ≤ 10¹² тем же перебором, что страница множителей.
Как пользоваться
Введите натуральное n. Получите φ(n). Проверка для малого n: переберите k = 1…n и посчитайте, у скольких НОД с n равен 1.
Примеры
Единица. φ(1) = 1.
Степень тройки. φ(9) = 6.
10. φ(10) = 4 (1, 3, 7, 9).
Ноль. Не считают.
Ещё значения
φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹ (p − 1). Для 8 = 2³ получите 4: нечётные 1, 3, 5, 7. Не пишите 8 − 1 = 7, путая с простым.
Мультипликативность: если НОД(a, b) = 1, то φ(ab) = φ(a)φ(b). φ(10) = φ(2)φ(5) = 1·4 = 4. Для 12 = 4·3 взаимно простых множителей φ(4)φ(3) = 2·2 = 4, и φ(12) = 4 (1, 5, 7, 11).
Сумма φ(d) по делителям d числа n равна n. Для n = 6 делители 1, 2, 3, 6: φ 1+1+2+2 = 6. Это проверка, не формула калькулятора.
Не путайте с следующим простым: после 8 простое 11, а φ(8) = 4. Разные вопросы.
Криптография часто берёт φ((p−1)(q−1)) для модуля pq. Эта страница считает одно n, не ключи и не «секретные p, q».
Большое простое вроде 1 000 003: если оно простое, φ = n − 1. Калькулятор сначала раскладывает; если множитель один — ответ n − 1. Проверку простоты без φ даёт простота.
φ(n) чётна для n ≥ 3. Если получили нечётный ответ при n ≥ 3, ошибка ввода. φ(1) и φ(2) — исключения 1 и 1.
Связь с степенью по модулю: a^{φ(m)} ≡ 1 (mod m) при взаимной простоте. Не используйте это как замену обратного: обратный — ax ≡ 1.
n = p q двух разных простых: φ = (p−1)(q−1). Для 15 = 3·5 получите 8. Числа 1, 2, 4, 7, 8, 11, 13, 14.
Не считайте φ как сумму цифр или как число делителей τ(n). У 12 делителей шесть, φ(12) = 4.
Отрицательное n не подают. Модуль |n| — не эта страница; знак к взаимной простоте на отрезке 1…n не относится.
Итог: одно натуральное n, одно φ(n). Пару чисел на взаимность проверяйте отдельно. Множители можно сверить разложением.
Ещё таблица малых n: φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4. Видно, что степень двойки даёт половину: φ(2ᵏ)=2ᵏ⁻¹. Не обобщайте «половина n» на нечётные: φ(9)=6, не 4,5.
Составное 21 = 3·7: φ = 2·6 = 12. Числа 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20. Пропуск кратных 3 и 7. Пересчёт вручную сверяет калькулятор.
Не берите φ как ответ «сколько простых до n». Простых до 10 четыре (2, 3, 5, 7), φ(10)=4 случайно совпало. До 9 простых четыре, φ(9)=6 — уже мимо.
Если задача «порядок группы вычетов взаимно простых с n», это как раз φ(n). Школьная формулировка — «сколько дробей a/n несократимы с 1 ≤ a ≤ n». Мост к отношению после сокращения на НОД.
n = 100: 100 = 2²·5², φ = 100·1/2·4/5 = 40. Не 99 и не 50. Степени входят только через вынесение (1−1/p), не через «минус все степени».
Школьные формулировки
«Сколько чисел от 1 до n не имеют с n общих простых множителей» — это φ(n). «Сколько правильных несократимых дробей со знаменателем n» — тоже φ(n), если числитель от 1 до n. Не отвечайте τ(n) с делителей.
«Доказать, что φ(2n)=φ(n) при нечётном n»: нечётный n взаимно прост с 2, мультипликативность даёт φ(2)φ(n)=φ(n). Калькулятор проверит числами: n=9, φ(9)=6, φ(18)=6. Для чётного n равенство ложно: φ(10)=4, φ(5)=4 совпало иначе; φ(12)=4, φ(6)=2.
Не используйте φ вместо следующего простого в задаче «найдите простое больше 20». И не вместо признака простоты самого n.
Проверка цепочкой: разложите n на множители, примените формулу вручную, сверьте с φ. Для 60 = 2²·3·5: 60·1/2·2/3·4/5 = 16. Калькулятор должен дать 16. Числа 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59 — шестнадцать штук, кратные 2, 3, 5 вычеркнуты.
Единица в формуле: каждый простой входит один раз. 16 = 2⁴, φ = 8, не «четыре раза (1−1/2)». Повтор множителя в разложении не умножает скобку повторно.
Типичные ошибки
- Писать φ(p) = p для простого p вместо p − 1.
- Считать φ(1) = 0.
- Путать с числом делителей.
- Применять φ(ab) = φ(a)φ(b) при НОД ≠ 1.
- Искать следующее простое в поле φ.
Частые вопросы
- Что такое функция Эйлера φ(n)?
- Это количество целых от 1 до n, взаимно простых с n. φ(1) = 1, φ(9) = 6, φ(10) = 4.
- Чему равна φ простого p?
- p − 1: все числа от 1 до p − 1 взаимно просты с p. Двойка даёт 1, семёрка — 6.
- Как связаны φ и взаимная простота?
- Пара проверяется на странице взаимной простоты. φ считает, сколько таких пар с фиксированным n.
- Нужно ли сначала раскладывать n?
- Калькулятор раскладывает сам. Смотреть множители отдельно удобно на разложении.
- Зачем φ в обратном по модулю?
- Теорема Эйлера: a^{φ(m)} ≡ 1 (mod m) при НОД(a, m) = 1. Сам обратный ищет обратный по модулю.
- Почему n = 0 запрещён?
- Функцию определяют для натуральных n ≥ 1. Ноль не входит.