Eulersche Phi-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.

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:

$\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)$

Beispiel:

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

Multiplikativität

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

$\varphi (mn)=\varphi (m)\varphi (n)$, 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

$n=\prod _{p\mid n}p^{k_{p}}$ (p ist Primzahl),

so gilt

$\varphi (n)=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}(1-{\frac {1}{p}})$

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:

$m\mid a^{\varphi (m)}-1$,

oder anders formuliert:

$a^{\varphi (m)}\equiv 1{\pmod {m}}$

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

$p\mid a^{p-1}-1$,

bzw.

$a^{p-1}\equiv 1{\pmod {p}}$

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