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

• Функция Эйлера $\mathrm{\phi }\left(𝑚\right)$ – это функция, значение которой равно количеству натуральных чисел, меньших либо равных m и взаимно простых с m.

• Например, для числа 33 существует 20 меньших его и взаимно простых с ним чисел (1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), поэтому $\mathrm{\phi }\left(33\right)=20$.

• Если число m представлено в виде простых сомножителей вида $𝑚={𝑝}_1^{{𝑎}_1}{𝑝}_2^{{𝑎}_2}\dots {𝑝}_{𝑘}^{{𝑎}_{𝑘}}$, то функцию Эйлера вычисляют по формуле:

$\mathrm{\phi }\left(𝑚\right)=\left({𝑝}_1^{{𝑎}_1}-{𝑝}_1^{{𝑎}_1-1}\right)\left({𝑝}_2^{{𝑎}_2}-{𝑝}_2^{{𝑎}_2-1}\right) \dots \left({𝑝}_{𝑘}^{{𝑎}_{𝑘}}-{𝑝}_{𝑘}^{{𝑎}_{𝑘}-1}\right).$

• Пример. $100=2^2\cdot 5^2$, тогда $\mathrm{\phi }\left(𝑚\right)=\left(2^2-2^1\right)\left(5^2-5^1\right)=40.$

• Для взаимно простых a и b чисел справедливо:

  $\mathrm{\phi }\left(𝑎𝑏\right)=\mathrm{\phi }\left(𝑎\right)\mathrm{\phi }\left(𝑏\right).$