Функция Эйлера

Определение. φ(n) — количество натуральных чисел от 1 до n, взаимно простых с n. Для простого p: φ(p) = p−1. Для N=pq: φ(N)=(p−1)(q−1).

В каких главах встречается

• Натуральные числа: от счёта до глубин теории чисел

Связанные концепты

Требуются перед изучением:

• Взаимная простота