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

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

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

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

Некоторые свойства

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