PROFILPELAJAR.COM

Функція Ейлера $\varphi (n)$ , де $n$ — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за $n$ і взаємно простих з ним.^{[[#cite_note-FOOTNOTERibenboim199634'"`UNIQ--templatestyles-00000004-QINU`"'<span_title="англійською_мовою"_class="ref-info">(англ.)-1|[1]]]}

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

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

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

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

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

$\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

Властивості

$\varphi (p^{n})=(p-1)p^{n-1}$ , якщо $p$ — просте число;^{[[#cite_note-FOOTNOTEСагалович200735—36Вычисление_функции_Эйлера'"`UNIQ--templatestyles-0000000C-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)-2|[2]]]}
$\varphi (mn)=\varphi (m)\varphi (n)$ , якщо $m$ і $n$ взаємно прості. Тобто Функція Ейлера мультиплікативна;^{[[#cite_note-FOOTNOTEBurton2007133Theorem_7.2'"`UNIQ--templatestyles-00000004-QINU`"'<span_title="англійською_мовою"_class="ref-info">(англ.)-3|[3]]]}
$a^{\varphi (m)}\equiv 1{\pmod {m}}$ , якщо $a$ і $m$ взаємно прості. Докладніше: Теорема Ейлера.^{[[#cite_note-FOOTNOTEЧандрасекхаран._Введение_в_аналитическую_теорию_чисел,_1974_'"`UNIQ--templatestyles-0000000C-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)-4|[4]]]}
$\varphi (m^{k})=m^{k-1}\varphi (m);$
$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)$ — найбільший спільний дільник.

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

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

Комп'ютерна реалізація

C++

Код на мові 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

Код на мові 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

Код на мові 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

Код вище при n= 6, 9... видає неправильний результат. Перевірено для Python 3.11 у Visual Studio Code

Наступний код працює коректно:

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

Код на мові 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

Див. також

Примітки

[[#cite_ref-FOOTNOTERibenboim199634'"`UNIQ--templatestyles-00000004-QINU`"'<span_title="англійською_мовою"_class="ref-info">(англ.)_1-0|↑]] Ribenboim, 1996, с. 34(англ.).
[[#cite_ref-FOOTNOTEСагалович200735—36Вычисление_функции_Эйлера'"`UNIQ--templatestyles-0000000C-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)_2-0|↑]] Сагалович, 2007, с. 35—36, Вычисление функции Эйлера(рос.).
[[#cite_ref-FOOTNOTEBurton2007133Theorem_7.2'"`UNIQ--templatestyles-00000004-QINU`"'<span_title="англійською_мовою"_class="ref-info">(англ.)_3-0|↑]] Burton, 2007, с. 133, Theorem 7.2(англ.).
[[#cite_ref-FOOTNOTEЧандрасекхаран._Введение_в_аналитическую_теорию_чисел,_1974_'"`UNIQ--templatestyles-0000000C-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)_4-0|↑]] Чандрасекхаран. Введение в аналитическую теорию чисел, 1974 (рос.).