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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Перша тисяча значень

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

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

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

Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритма шифрування 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. , якщо — просте число;[2]
  2. , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна;[3]
  3. , якщо і взаємно прості. Докладніше: Теорема Ейлера.[4]
  4. , , , якщо найменше спільне кратне, a найбільший спільний дільник.

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

  1. де — деяка константа;

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

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

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

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

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

  1. Ribenboim, 1996, с. 34(англ.)
  2. Сагалович, 2007, с. 35—36, Вычисление функции Эйлера(рос.)
  3. Burton, 2007, с. 133, Theorem 7.2(англ.)
  4. Чандрасекхаран. Введение в аналитическую теорию чисел, 1974 (рос.)

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