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

Первая тысяча значений $\varphi(n)$

Функция Эйлера $\varphi(n)$, где $n$ — натуральное число, равна количеству натуральных чисел, меньших $n$ и взаимно простых с ним. Названа в честь Эйлера, который впервые использовал ее в своих работах по теории чисел.

Вычисление функции Эйлера

Пусть дано натуральное число $n\,$, представленное в виде его канонического разложения на простые сомножители $p_i:\,$

$n = \prod_{i=1}^k p_i^{\alpha_i}$

Тогда функция Эйлера может быть вычислена по формуле

$\varphi(n) = \prod_{i=1}^k p_i^{\alpha_i - 1} \left( p_i - 1 \right)$

. При этом полагается, что

$\varphi(1) = 1.$

Функцию Эйлера можно также представить в виде так называемого произведения Эйлера:

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),$

где $p$ — простое число и пробегает все значения, участвующие в разложении $n$ на простые сомножители.

Также иногда функцией Эйлера называют функцию от рационального числа $q\in(-1,1)$:

$\varphi(q)=\prod_{k=1}^\infty(1-q^k),$

однако в этой статье о ней речь не идет.

Некоторые значения функции

$\varphi(n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Свойства

1. $\varphi(p^n)=p^{n-1}(p-1)$, если $p$ — простое число. В частности, при $n=1$ имеем $\varphi(p)=p-1$;
2. $\varphi(mn)=\varphi(m)\varphi(n)$, если $m$ и $n$ взаимно просты. То есть Функция Эйлера мультипликативна;
3. $a^{\varphi(m)}\equiv 1\pmod m$, если $a$ и $m$ взаимно просты. Так называемая теорема Эйлера;
4. $\varphi(m^k)=m^{k-1}\varphi(m);$
5. $mn=(m,\;n)[m,\;n], \varphi(m)\varphi(n)=\varphi((m,\;n))\varphi([m,\;n]), \varphi(mn)\varphi((m,\;n))=\varphi(m)\varphi(n)(m,\;n)$, если $[m,\;n]$ — наименьшее общее кратное, a $(m,\;n)$ — наибольший общий делитель.

Асимптотические соотношения

1. $\frac{Cn}{\ln\ln n}\leqslant\varphi(n)\leqslant n,$ где $C$ — некоторая константа;
2. $\sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x);$
3. $\sum_{k=1}^n\frac{k}{\varphi(k)}=O(n);$
4. $\sum_{k=1}^n\frac{1}{\varphi(k)}=O(\ln n).$

Аналитические соотношения

• Функция Эйлера имеет взаимосвязь с функцией Мёбиуса:

• $\varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right);$
• $\sum_{k=1}^n\varphi(k)=\frac{1}{2}\left(1+\sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right);$
• $\sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor;$
• $\sum_{d\mid n}\frac{\mu^2(d)}{\varphi(d)}=\frac{n}{\varphi(n)}.$

• $\sum_{d\mid n,\; d\in N}\varphi(d)=n.$
• Ряд Дирихле с коэффициентами $\varphi(n)$ можно представить через дзета-функцию Римана:

  $\sum_{n=1}^\infty\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.$

• Сумма ряда Ламберта с коэффициентами вида $\varphi(n)$:

  $\sum_{n=1}^\infty\frac{\varphi(n)q^n}{1-q^n}=\frac{q}{(1-q)^2},$

где $|q|<1$.

• $\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n)$, где $n>1$.

См. также

• Список объектов, названных в честь Леонарда Эйлера