Die eulersche Phi-Funktion

Die Formeln werden nur mit aktiviertem JavaScript korrekt dargestellt.
Die Fensterbreite des Browsers sollte 800 Pixel nicht unterschreiten. Auf Smartphones ist das Querformat deutlich besser zu lesen.

Datenschutzerklärung    Impressum    Gesamtübersicht    © Jakob Fechtig
 

Inhalt

Definition
Auf Primzahlen angewendet
Formel für Zahlen, die keine Primzahlen sind

  Definition

Wir suchen zu einer natürlichen Zahl die Anzahl aller Zahlen, die kleiner sind, als diese Zahl und zu ihr teilerfremd.
Wir schreiben: $$ \phi(a) $$

Zur Erinnerung:
Zwei natürliche Zahlen a und b sind teilerfremd, wenn $$ ggT(a, b)=1 $$ gilt.

Beispiel:
Wir suchen $\phi(10)$. Probieren wir mit dem Algorithmus von Euklid die natürlichen Zahlen < 10 durch: $$ \begin{array}{} 10 &:& 9&=&1 \text{ Rest }1\\ 9 &:& 1&=&9 \text{ Rest }0&ggT(10,9)=1\\ \\ 10 &:& 8&=&1 \text{ Rest }2\\ 8 &:& 2&=&4 \text{ Rest }0&ggT(10,8)=2\\ \\ 10 &:& 7&=&1 \text{ Rest }3\\ 7 &:& 3&=&2 \text{ Rest }1\\ 3&:&1&=&3\text{ Rest }0 &ggT(10,7)=1\\ \\ 10 &:& 6&=&1 \text{ Rest }4\\ 6 &:& 4&=&1 \text{ Rest }2\\ 4&:&2&=&2\text{ Rest }0 &ggT(10,6)=2\\ \\ 10 &:& 5&=&2 \text{ Rest }0&ggT(10,5)=2\\ \\ 10 &:& 4&=&2 \text{ Rest }2\\ 4 &:& 2&=&2 \text{ Rest }0&ggT(10,4)=2\\ \\ 10 &:& 3&=&3 \text{ Rest }1\\ 3 &:& 1&=&3 \text{ Rest }0 &ggT(10,3)=1\\ \\ 10 &:& 2&=&5 \text{ Rest }0&ggT(10,2)=2\\ \\ 10 &:& 1&=&10 \text{ Rest }0&ggT(10,1)=1\\ \\ \end{array} $$ Anmerkung: Die 1 wird gerne vergessen. Sie ist zu allen natürlichen Zahlen (auch sich selbst) teilerfremd. Nun zählen wir, wie oft der ggT den Wert 1 ergeben hat. Wir kommen auf 4. Das bedeutet: $$ \phi(10)=4 $$ Diese Berechnung war recht aufwändig. Wir sollten einen kürzeren Weg finden!

  Auf Primzahlen angewendet

Primzahlen müssen durch ihre Definition bedingt zu allen natürlichen Zahlen, die kleiner sind als sie selbst teilerfremd sein.
Noch einmal zur Erinnerung: Die 1 ist zu allen natürlichen Zahlen teilerfremd. Für jede Primzahl p gilt: $$ \phi(p)=p-1 $$

Für die Potenzen von Primzahlen gilt die Formel: $$ \phi(p^n)=p^n-p^{n-1} $$

  Formel für Zahlen, die keine Primzahlen sind

Die folgende Formel berechnet $\phi(a)$ für alle Zahlen, die keine Primzahlen sind: $$ \phi(a)=({p_1}^{e_1} - {p_1}^{e_1 - 1}) \cdot ({p_2}^{e_2} - {p_2}^{e_2 - 1}) \cdot ... \cdot ({p_n}^{e_n} - {p_n}^{e_n - 1}) $$ Wobei $p_1$ bis $p_n$ die Primfaktoren von $a$ mit den passenden Exponenten $e_1$ bis $e_n$ sind.

Beispielrechnung:
Gesucht: $$ \phi(48) $$ Primfaktorzerlegung: $$ 48 = 2^4 \cdot 3^1 $$ Berechnung von $\phi(48)$: $$ \begin{array}{} \phi(48) &=& (2^4 - 2^3) \cdot (3^1 - 3^0)\\ ~ &=& (16 - 8) \cdot (3 - 1)\\ ~ &=& 8 \cdot 2\\ ~ &=& 16 \end{array} $$
Zur Probe zählen wir einfach die teilfremden Zahlen $<48$: $$ \begin{array}{} \{&1,&5,&7,&11,&13,&17,&19,&23,&25,&29,&31,&35,&37,&41,&43,&47&\}\\ ~&1,&2,&3,&4,&5,&6,&7,&8,&9,&10,&11,&12,&13,&14,&15,&16&~\\ \end{array} $$