Функція Ейлера , де  — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за і взаємно простих з ним. Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:

Перша тисяча значень

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

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

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

ред.
  +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.  , якщо   — просте число;[[#cite_note-FOOTNOTEСагалович200735—36Вычисление_функции_Эйлера'"`UNIQ--templatestyles-00000009-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)</span>-1|[1]]]
  2.  , якщо   і   взаємно прості. Тобто Функція Ейлера мультиплікативна;[[#cite_note-FOOTNOTEBurton2007133Theorem_7.2'"`UNIQ--templatestyles-0000000F-QINU`"'<span_title="англійською_мовою"_class="ref-info">(англ.)</span>-2|[2]]]
  3.  , якщо   і   взаємно прості. Докладніше: Теорема Ейлера.[[#cite_note-FOOTNOTEЧандрасекхаран._Введение_в_аналитическую_теорию_чисел,_1974_'"`UNIQ--templatestyles-00000009-QINU`"'<span_title="російською_мовою"_class="ref-info">(рос.)</span>-3|[3]]]
  4.  
  5.  ,  ,  , якщо  найменше спільне кратне, a  найбільший спільний дільник.

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

ред.
  1.   де   — деяка константа;
  2.  
  3.  
  4.  

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

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

Код вище при 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
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

Див. також

ред.

Примітки

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

Посилання

ред.