Eulersche φ-Funktion

Die eulersche Phi-Funktion ist eine zahlentheoretische Funktion. Sie ordnet jeder natürlichen Zahl n die Anzahl der natürlichen Zahlen a von 1 bis n zu, die zu n teilerfremd sind, für die also ggT(a,n) = 1 ist.

Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben φ (Phi) bezeichnet.

Inhaltsverzeichnis

1 Beispiele 2 Berechnung 2.1 Primzahlen 2.2 Potenz von Primzahlen 2.3 Multiplikativität 2.4 Zusammengesetzte Zahlen 3 Bedeutung der φ-Funktion 4 Weblinks

Beispiele

• Die Zahl 6 ist zu 2 Zahlen zwischen 1 und 6 teilerfremd (1 und 5), also ist φ(6) = 2.
• Die Zahl 13 ist als Primzahl zu den 12 Zahlen von 1 bis 12 teilerfremd, also ist φ(13) = 12.
• Die ersten 18 Werte der φ-Funktion lauten:

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

Berechnung

Primzahlen

Da alle Primzahlen p nur durch 1 und sich selbst teilbar sind, sind sie sicher zu den Zahlen 1 bis p-1 teilerfremd, daher ist φ(p) = p-1.

Potenz von Primzahlen

Eine Potenz p^k aus einer Primzahl und einer natürlichen Zahl k ist nur zu Vielfachen von p nicht teilerfremd. Es gibt p^k-1 Vielfache von p, die kleiner oder gleich p^k sind (1*p, 2*p, ..., p^α-1*p). Daher gilt:

Beispiel:

φ(16) = φ(2⁴) = 2⁴ - 2³ = 2³ * (2 - 1) = 8 * 1 = 8

Multiplikativität

Die φ-Funktion ist multiplikativ für teilerfremde natürliche Zahlen:

, falls ggT(m, n) = 1

Beispiel:

φ(18) = φ(2)*φ(9) = 1*6 = 6

Gegenbeispiel für Zahlen m und n mit gemeinsamem Primfaktor:

φ(2*4) = φ(8) = 4, aber φ(2)*φ(4) = 1*2 = 2.

Zusammengesetzte Zahlen

Die Berechnung von φ(n) für zusammengesetzte Zahlen n ergibt sich aus der Multiplikativität. Hat n die kanonische Darstellung

(p ist Primzahl),

so gilt

Beispiel:

φ(72) = φ(2³*3²) = 2^3-1(2-1) * 3^2-1(3-1) = 2² * 1 * 3 * 2 = 24

Bedeutung der φ-Funktion

Eine der wichtigsten Anwendungen findet die φ-Funktion im Satz von Fermat-Euler:

Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind, gilt:

,

oder anders formuliert:

Ein Spezialfall (für Primzahlen m) dieses Satzes ist der Kleine Fermatsche Satz:

,

bzw.

Der Satz von Fermat-Euler findet u.a. Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Weblinks

• Ausführlicher Artikel zur φ-Funktion
• Programme zur φ-Funktion

See also: Eulersche φ-Funktion, Ganze Zahlen, Größter gemeinsamer Teiler, Kleiner fermatscher Satz, Kryptographie, Leonhard Euler, Natürliche Zahl, Phi, Potenz (Mathematik), Primfaktorzerlegung