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

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

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

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