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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Перша тисяча значень \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;
}

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.

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