Функція Ейлера

Перша тисяча значень $\phi (n)$

Функція Ейлера $\phi (n)$, де $n$ — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за $n$ і взаємно простих з ним.Шаблон:Sfn

Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:

$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p}),$

де $p$ — просте число.

Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритма шифрування RSA.

Деякі значення функції

$\phi (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. $\phi (p^n)=(p-1)p^{n-1}$, якщо $p$ — просте число;Шаблон:Sfn
2. $\phi (mn)=\phi (m)\phi (n)$, якщо $m$ і $n$ взаємно прості. Тобто Функція Ейлера мультиплікативна;Шаблон:Sfn
3. $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$, якщо $a$ і $m$ взаємно прості. Докладніше: Теорема Ейлера.Шаблон:Sfn
4. $\phi (m^k)=m^{k-1}\phi (m);$
5. $mn=(m,n)[m,n]$, $\phi (m)\phi (n)=\phi ((m,n))\phi ([m,n])$, $\phi (mn)\phi ((m,n))=\phi (m)\phi (n)(m,n)$, якщо $[m,n]$ — найменше спільне кратне, a $(m,n)$ — найбільший спільний дільник.

Асимптотичні відношення

1. $\frac{Cn}{\ln \ln n}⩽\phi (n)⩽n,$ де $C$ — деяка константа;
2. $\sum _{n⩽x}\phi (n)=\frac{3}{{\pi }^2}{x}^2+O(x\ln x);$
3. $\sum _{k=1}^n\frac{k}{\phi (k)}=O(n);$
4. $\sum _{k=1}^n\frac{1}{\phi (k)}=O(\ln n).$

Див. також

• Псі-функція Дедекінда
• Теорема Ейлера (теорія чисел)
• Функція Мебіуса

Посилання

• Онлайн обчислювач функції Ейлера на JavaScript - до 20 цифр Шаблон:Ref-en