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

Определение:

Функция Эйлера от натурального числа [math]n[/math] возвращает количество натуральных чисел, не превосходящих [math]n[/math], и взаимно простых с ним.

Обозначают [math]\phi(n)[/math].

Свойства

• [math]\phi(p^a)=p^a(p-1)[/math], где [math]p\in\mathbb{P}[/math],
• Мультипликативность: [math]\phi(mn)=\phi(m)\phi(n)[/math] для взаимно простых [math]m[/math] и [math]n[/math],
• Теорема Эйлера: [math]a^{\phi(n)}=1 \pmod n[/math] для [math]a[/math] и [math]n[/math] взаимно простых,
• [math]\phi(m^k)=m^{k-1}\phi(m) [/math].