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

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

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

Функция Эйлера [math]\varphi (a) [/math] определяется для всех целых положительных a и представляет собою число чисел ряда [math]0, 1, \ldots, a-1 [/math], взаимно простых с a.

Примеры:

[math] \varphi (1) = 1[/math], [math] \varphi (4) = 2[/math],
[math] \varphi (2) = 1[/math], [math] \varphi (5) = 4[/math],
[math] \varphi (3) = 2[/math], [math] \varphi (6) = 2[/math].

Свойства функции Эйлера

• 1. Доказательство: [math] \varphi (p) = p-1 [/math], p — простое, [math] \varphi (p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}[/math].
  • Логически понятно, если строго, то выводится из 2 свойства.
• 2. Пусть [math] a = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \ldots {p_k}^{\alpha_k}[/math] — каноническое разложение числа a, тогда

[math] \varphi (a) = a(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_k})[/math].

• • Доказательство: Пусть [math] x [/math] пробегает числа [math] 0,1,2,\ldots,a-1[/math], положим [math] \sigma_x = (a, x)[/math] — НОД. Тогда [math] \varphi(a) [/math] есть число значений [math] \sigma_x [/math], равных единице. Возьмем функцию, которая равна единице, если [math] \sigma_x = 1[/math], и равна нулю в остальных случаях. Вот такая функция : [math]\sum_{d | n} \mu(d) = \begin{cases} 1,&n=1,\\ 0,&n\gt 1.\end{cases}[/math], где [math] \mu(a) [/math] — функция Мебиуса. Отсюда [math] \varphi(a) = \sum_{0 \le x \le a-1}(\sum_{d | a} \mu(d))[/math]. Поскольку справа сумма в скобках берется по всем делителям d числа [math] \sigma_x = ( x , a )[/math], то d делит x и a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел [math] 0,1,2,\ldots,a-1[/math] ровно [math] \frac{a}{d} [/math] штук. Получается, что [math] \varphi(a) = \sum_{d | a} \frac{a}{d}\mu(d) = a\sum_{d | a} \frac{\mu(d)}{d} = a(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_k})[/math].

• 3. Функция Эйлера является мультипликативной [math] \varphi(a_1 a_2) = \varphi(a_1)\varphi(a_2) [/math].
  • Вытекает из первого свойства.

Еще примеры

• [math] \varphi(60) = 60(1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{5}) = 16[/math]
• [math] \varphi(81) = 81 - 27 = 54 [/math]