Математика • 11 класс

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

Функция Эйлера $φ (m)$ – это функция, значение которой равно количеству натуральных чисел, меньших либо равных m и взаимно простых с m.
Например, для числа 33 существует 20 меньших его и взаимно простых с ним чисел (1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), поэтому $φ (33) = 20$ .
Если число m представлено в виде простых сомножителей вида $m = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ , то функцию Эйлера вычисляют по формуле:
$φ (m) = (p_{1}^{a_{1}} - p_{1}^{a_{1} - 1}) (p_{2}^{a_{2}} - p_{2}^{a_{2} - 1}) \dots (p_{k}^{a_{k}} - p_{k}^{a_{k} - 1}) .$
Пример. $100 = 2^{2} \cdot 5^{2}$ , тогда $φ (m) = (2^{2} - 2^{1}) (5^{2} - 5^{1}) = 40 .$
Для взаимно простых a и b чисел справедливо:
$φ (a b) = φ (a) φ (b) .$