Zuletzt aktualisiert: 2026-07-13

Definition

Die eulersche Phi-Funktion $\varphi(n)$ zählt, wie viele der ganzen Zahlen von $1$ bis $n$ zu $n$ teilerfremd sind – also außer $1$ keinen gemeinsamen Teiler mit $n$ haben. Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler $1$ ist.

Zum Beispiel ist $\varphi(9) = 6$: Unter $1, 2, \dots, 9$ sind $1, 2, 4, 5, 7, 8$ teilerfremd zu $9$, während $3, 6, 9$ es nicht sind.

Die Funktion ist nach Leonhard Euler benannt, der sie 1763 einführte. Sie wird auch $\phi(n)$ geschrieben und Phi-Funktion genannt.

Die Produktformel

Man muss keineswegs jede Zahl bis $n$ prüfen. Sobald $n$ in seine verschiedenen Primfaktoren zerlegt ist, ergibt sich der Totient unmittelbar:

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

Das Produkt läuft über die verschiedenen Primzahlen, die $n$ teilen – die Exponenten treten nicht auf. Jede Primzahl $p$ entfernt den Anteil $1/p$ der Zahlen (die durch $p$ teilbaren), und da die Primzahlen unabhängig wirken, multiplizieren sich die Anteile.

Beispielrechnung – n = 36. Die Primfaktorzerlegung ist $36 = 2^2 \cdot 3^2$, die verschiedenen Primzahlen sind also $2$ und $3$:

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

Die zwölf zu $36$ teilerfremden Zahlen sind $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

Primzahlen und Primzahlpotenzen

Zwei Grundfälle machen die Formel leicht nachvollziehbar:

• Primzahl $p$: Jede ganze Zahl von $1$ bis $p - 1$ ist teilerfremd zu $p$, also $\varphi(p) = p - 1$. Etwa $\varphi(7) = 6$.
• Primzahlpotenz $p^k$: Nicht teilerfremd zu $p^k$ sind nur die Vielfachen von $p$, davon gibt es $p^{k-1}$. Daher

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

So ist $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ und $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

Multiplikativität

Der Totient ist multiplikativ: Sind $m$ und $n$ teilerfremd, so gilt

$\varphi(mn) = \varphi(m)\,\varphi(n)$

Genau deshalb funktioniert die Produktformel – man schreibt $n$ als Produkt von Primzahlpotenzen, wendet $\varphi(p^k) = p^{k-1}(p-1)$ auf jede an und multipliziert. Etwa $36 = 4 \cdot 9$ mit $\gcd(4, 9) = 1$, also $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

Man beachte die Teilerfremdheitsbedingung: $\varphi(mn) = \varphi(m)\varphi(n)$ kann versagen, wenn $m$ und $n$ einen Faktor gemeinsam haben. So ist $\varphi(2 \cdot 2) = \varphi(4) = 2$, nicht $\varphi(2)\varphi(2) = 1$.

Der Satz von Euler

Der Totient bestimmt die modulare Potenzierung. Der Satz von Euler besagt: Ist $\gcd(a, n) = 1$, so gilt

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

Dies verallgemeinert den kleinen Satz von Fermat ($a^{p-1} \equiv 1 \pmod p$ für eine Primzahl $p$), der genau der Spezialfall $n = p$ mit $\varphi(p) = p - 1$ ist.

Beispiel. Sei $a = 3$, $n = 10$. Hier ist $\varphi(10) = 4$, also $3^4 = 81 \equiv 1 \pmod{10}$ – und tatsächlich endet $81$ auf $1$. Der Satz erlaubt es, riesige Exponenten vor der Rechnung modulo $\varphi(n)$ zu reduzieren.

Anwendung bei RSA

Die RSA-Public-Key-Kryptografie baut unmittelbar auf dem Totient auf. Ein Modul wird aus zwei großen Primzahlen als $n = p \cdot q$ gebildet, sodass

$\varphi(n) = (p - 1)(q - 1)$

Der öffentliche Exponent $e$ und der private Exponent $d$ werden so gewählt, dass $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Der Satz von Euler garantiert dann, dass das Entschlüsseln das Verschlüsseln rückgängig macht: $(m^e)^d \equiv m \pmod n$.

Die Sicherheit beruht auf einer Lücke: Jeder kann $n$ veröffentlichen, aber $\varphi(n) = (p-1)(q-1)$ zu berechnen setzt die Kenntnis von $p$ und $q$ voraus. Diese allein aus $n$ zurückzugewinnen bedeutet, ein großes Semiprim zu faktorisieren – was für hinreichend große Primzahlen als praktisch nicht durchführbar gilt. Tatsächlich ist $\varphi(n)$ zu kennen gleichbedeutend damit, $n$ zu faktorisieren.

Beispiele

$n$	Zerlegung	Produktform	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (prim)	$101\,(1 - \tfrac{1}{101})$	$100$

Sonderfälle

• $n = 1$: Per Konvention ist $\varphi(1) = 1$. Die einzige Zahl im Bereich, $1$, ist zu sich selbst teilerfremd.
• $n$ prim: $\varphi(n) = n - 1$, das Maximum für diese Größe – Primzahlen haben die meisten teilerfremden Reste.
• $n$ gerade: Der Faktor $(1 - \tfrac12)$ entfernt mindestens die Hälfte der Zahlen, also $\varphi(n) \le n/2$.
• Summe über Teiler: Die Totienten aller Teiler von $n$ ergeben zusammen $n$ selbst: $\sum_{d \mid n} \varphi(d) = n$. Für $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

Kurzübersicht

Begriff	Formel
Definition	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
Produktformel	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
Primzahl	$\varphi(p) = p - 1$
Primzahlpotenz	$\varphi(p^k) = p^{k-1}(p - 1)$
Multiplikativ	$\varphi(mn) = \varphi(m)\varphi(n)$ falls $\gcd(m, n) = 1$
Satz von Euler	$a^{\varphi(n)} \equiv 1 \pmod n$ falls $\gcd(a, n) = 1$
Teilersumme	$\sum_{d \mid n} \varphi(d) = n$

Häufig gestellte Fragen (FAQ)

Was ist die eulersche Phi-Funktion?

Die eulersche Phi-Funktion φ(n) zählt die positiven ganzen Zahlen bis n, die zu n teilerfremd sind – also außer 1 keinen gemeinsamen Teiler mit n haben. Zum Beispiel ist φ(9) = 6, denn 1, 2, 4, 5, 7 und 8 sind jeweils teilerfremd zu 9, während 3, 6 und 9 es nicht sind. Per Konvention ist φ(1) = 1.

Wie berechnet man φ(n)?

Zerlegen Sie n in seine verschiedenen Primzahlen p₁, p₂, …, pₖ und wenden Sie φ(n) = n · ∏(1 − 1/p) über diese Primzahlen an. Für n = 36 = 2² · 3² ergibt sich φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. Es zählen nur die verschiedenen Primzahlen, nicht ihre Exponenten.

Was ist der Totient einer Primzahl?

Für eine Primzahl p ist jede ganze Zahl von 1 bis p − 1 teilerfremd zu p, also φ(p) = p − 1. Für eine Primzahlpotenz pᵏ liefert die Formel φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). Zum Beispiel φ(7) = 6 und φ(8) = φ(2³) = 8 − 4 = 4.

Warum ist der Totient bei RSA und dem Satz von Euler wichtig?

Der Satz von Euler besagt: Ist ggT(a, n) = 1, so gilt a^φ(n) ≡ 1 (mod n) – eine Verallgemeinerung des kleinen Satzes von Fermat. RSA beruht darauf: Für einen Modul n = p·q aus zwei Primzahlen ist φ(n) = (p − 1)(q − 1), und der öffentliche und der private Exponent werden so gewählt, dass e·d ≡ 1 (mod φ(n)). φ(n) zu kennen ist gleichbedeutend damit, n zu faktorisieren – und genau das macht RSA sicher.