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

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

где – простые делители в каноническом разложении числа а .

Число чисел, составляющих приведенную систему вычетов равно φ (m).