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

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

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

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

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

Властивості

1. $\varphi(p^n)=(p-1)p^{n-1}$, якщо $p$ — просте число;
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).$

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

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;
}

Паскаль

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.

Посилання

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