Функция Эйлера φ(n), где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним. Названа в честь Эйлера, который впервые использовал ее в своих работах по теории чисел.

Определение

Пусть дано натуральное число , представленное в виде его канонического разложения на простые сомножители

Тогда функция

называется функцией Эйлера. При этом полагается, что

φ(1) = 1.

Функцию Эйлера можно также представить в виде так называемого произведения Эйлера:

где p — простое число и пробегает все значения, участвующие в разложении n на простые сомножители.

Также иногда функцией Эйлера называют функцию от рационального числа :

однако в этой статье о ней речь не идет.

Некоторые значения функции

φ(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. φ(pn) = pn − 1(p − 1), если p — простое число. В частности, при n = 1 имеем φ(p) = p − 1;
  2. φ(mn) = φ(m)φ(n), если m и n взаимно просты. То есть Функция Эйлера мультипликативна;
  3. , если a и m взаимно просты. Так называемая теорема Эйлера;
  4. φ(mk) = mk − 1φ(m);
  5. , если  — наименьшее общее кратное, a  — наибольший общий делитель.

Асимптотические соотношения

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

Аналитические соотношения

где | q | < 1.