Через простые множители
Произведение берётся по различным простым делителям n. Для простого p получается p − 1.
φ(n) = n × ∏ (1 − 1/p)
Сколько чисел меньше n взаимно просты с ним
φ(10) = 4: это 1, 3, 7 и 9. Формула n × ∏ (1 − 1/p) по разным простым делителям. Повтор простого в разложении берётся один раз в произведении, но степень в n остаётся.
Функция всплывает в обратном по модулю: обратное есть, когда φ-условие взаимной простоты выполнено, то есть НОД равен 1.
Откуда брать числа
- Число
Пример
φ(10) = 4. Это числа 1, 3, 7 и 9.
Вопросы
φ(1) чему равно?
Единице: число 1 взаимно просто само с собой по этому определению.
Зачем это?
Функция встречается в теореме Эйлера и в подсчёте обратимых остатков по модулю.
Нужно ли само разложение на экране?
Нет, показывается только значение φ(n). Множители смотрите в калькуляторе простого числа.