Функція Ейлера , де  — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за і взаємно простих з ним.[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.  
  5.  ,  ,  , якщо  найменше спільне кратне, a  найбільший спільний дільник.

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

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

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

C++ ред.

Pascal ред.

Python ред.

Ruby ред.

Див. також ред.

Примітки ред.

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

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