Функція Ейлера — Вікіпедія

Функція Ейлера ${\displaystyle \varphi (n)}$, де ${\displaystyle n}$ — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за ${\displaystyle n}$ і взаємно простих з ним.^[1]

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

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

де ${\displaystyle p}$ — просте число.

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

Деякі значення функції[ред. | ред. код]

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

Асимптотичні відношення[ред. | ред. код]

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

Комп'ютерна реалізація[ред. | ред. код]

C++[ред. | ред. код]

int phi(int n) { 	int ret = 1; 	for(int i = 2; i * i <= n; ++i) { 		int p = 1; 		while(n % i == 0) { 			p *= i; 			n /= i; 		} 		if((p /= i) >= 1) ret *= p * (i - 1); 	} 	return --n ? n * ret : ret; } 

Pascal[ред. | ред. код]

function gcd (A,B: longint): longint; begin   while (A <> B) do   begin     if (A > B) then        Dec(A, B)     else        Dec(B, A);   end;   gcd := A; end;  var   N: longint;   I,A: longint;  begin   WriteLn ('Input N: ');   ReadLn (N);   A := 0;   for I := 1 to N-1 do     if (gcd(I, N) = 1) then       Inc (A);   WriteLn ('The Euler Function of N is: ', A);   ReadLn; end. 

Python[ред. | ред. код]

def euler_function(n):     ret = 1     for i in range(2, math.floor(n**0.5)):         p = 1         while not n % i:             p *= i             n /= i         p /= i         if p >= 1:             ret = ret * p * (i - 1)     n -= 1     return n * ret if n else ret 

def euler_function(n):     ret = 1     i = 2     while i*i <= n:         p = 1         while not n % i:             p *= i             n /= i         p /= i         if p >= 1:             ret = ret * p * (i - 1)         i += 1     n -= 1     return n * ret if n else ret 

Ruby[ред. | ред. код]

def euler_function(n):     ret = 1     for i in range(2, math.floor(n**0.5)):         p = 1         while not n % i:             p *= i             n /= i         p /= i         if p >= 1:             ret = ret * p * (i - 1)     n -= 1     return n * ret if n else ret 

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

• Онлайн обчислювач функції Ейлера на JavaScript - до 20 цифр (англ.)

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.