Euler-Funktion

Die Eulersche φ-Funktion

Die Euler-Funktion oder Eulersche φ-Funktion ist eine sehr wichtige zahlentheoretische Funktion, die eine tiefe Beziehung zu Primzahlen und zu der so genannten Ordnung ganzer Zahlen hat.

Die Euler-Funktion φ: IN → IN ist eine Abbildung, die jeder natürlichen Zahl n die Anzahl φ(n) der zu n teilerfremden Zahlen m ≤ n zuordnet. (Anders ausgedrückt: φ(n) ist die Anzahl der Zahlen m ≤ n mit ggT(m, n) = 1.) Z.B. ist φ(6) = 2 (denn nur 1 und 5 sind teilerfremd zu 6), oder φ(15) = 8 (denn 1, 2, 4, 7, 8, 11, 13, und 14 sind teilerfremd zu 15). Die folgende Wertetabelle gibt die Funktionswerte für die ersten natürlichen Zahlen an.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8

Entdecken Sie eine Gesetzmäßigkeit? Falls ja, sollten Sie unbedingt weiter forschen, denn Sie könnten bisher noch offenen Problemen der Zahlentheorie auf den Grund kommen... Falls nicht, interessieren Sie vielleicht einige der wichtigsten bekannten Eigenschaften der Euler-Funktion. Die erste ist, dass es eine Formel gibt, mit der man φ(n) ausrechnen kann: Ist die Primfaktorzerlegung von n gegeben durch n = p₁^a₁ ... p_k^a_k, so gilt

φ(n) = n (1 - 1/p₁) ... (1 - 1/p_k).

Beispiel: 12 = 2² · 3, also φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 2 / (2 · 3) = 4. Eine weitere Eigenschaft der Euler-Funktion ist die Summenformel: Die Summe über die Euler-Funktionswerte φ(d) aller Teiler d einer Zahl n ergibt genau n, z.B. für n=12:

φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12.

Außerdem teilt die Ordnung ord_n(m) einer Zahl m modulo n stets φ(n). Eng verknüpft mit der Euler-Funktion ist die Carmichael-Funktion λ.

Literatur

Friedhelm Padberg: Elementare Zahlentheorie. Spektrum Akademischer Verlag, Heidelberg Berlin 1996
Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser Boston Basel Berlin 1994