φ-Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen zu ihr teilerfremd sind.

Die Bestimmung:

Sei eine natürliche Zahl gegeben, die in Form ihrer kanonischen Zerlegung in einfache Faktoren dargestellt ist

Dann die Funktion

Nennt man die eulersche Funktion. Dabei wurde gemeint, dass

φ(1) = 1.

Die eulersche Funktion kann man auch in Form des sogenannten eulerschen Produkts darstellen

wo p — eine Primzahl ist und durchläuft alle Bedeutungen, die an Zerlegung von n in Primfaktoren teilnehmen.

Auch die eulersche Funktion nennt man die Funktion der Rationalzahl :

Aber in diesem Artikel geht die Rede darum nicht.

Einige Funktionswerte

φ(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

Eigenschaften

  1. φ(pn) = pn − 1(p − 1), wenn p — eine Primzahl ist. Und bei n = 1 haben wir φ(p) = p − 1;
  2. φ(mn) = φ(m)φ(n), wenn m und n teilerfremd sind. D.h die eulersche Funktion ist multiplikativ;
  3. , wenn a und m teilerfremd sind. Das so genannte eulersche Theorem;
  4. φ(mk) = mk − 1φ(m);
  5. , wenn  — kleinstes gemeinsames Vielfaches, und  — größter gemeinsamer Teiler ist.

Asymptotische Verhältnisse

  1. wo C — eine gewisse Konstante ist;

Analztische Verhältnisse

wo | q | < 1.