Wikipedia · einfach zusammengefasst · Stand
Eulersche Phi-Funktion
Die Eulersche Phi-Funktion (andere Schreibweise: eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion.
Inhalt5 Abschnitte
Grundidee und Definition
Die eulersche Phi-Funktion \varphi ist eine zahlentheoretische Funktion. Sie ordnet jeder positiven natürlichen Zahl n die Anzahl der positiven natürlichen Zahlen zu, die höchstens n sind und zu n teilerfremd sind. Zwei Zahlen heißen teilerfremd, wenn ihr größter gemeinsamer Teiler \operatorname{ggT} gleich 1 ist. Der Wert \varphi(n) heißt auch Totient von n.
Formal gilt: \varphi:\mathbb N^+\to\mathbb N^+,\qquad \varphi(n)=\left|\{a\in\mathbb N\mid 1\le a\le n\land\operatorname{ggT}(a,n)=1\}\right|. Gleichwertig lässt sich die Anzahl als Summe schreiben: \varphi(n)=\sum_{\substack{1\le a\le n\\ \operatorname{ggT}(a,n)=1}}1. Der Funktionswert ist zugleich die Anzahl der zu n teilerfremden Reste modulo n. Für n>1 gilt 1\le\varphi(n)<n.
Einfache Beispiele
\varphi(1)=1, denn 1 hat keinen Primfaktor und ist auch zu sich selbst teilerfremd.
Für n=6 sind unter den Zahlen von 1 bis 6 nur 1 und 5 teilerfremd zu 6. Deshalb ist \varphi(6)=2.
Ist p eine Primzahl, so sind alle Zahlen von 1 bis p-1 teilerfremd zu p, aber p selbst nicht. Daher gilt für jede Primzahl: \varphi(p)=p-1. Beispielsweise ist \varphi(13)=12.
Berechnung mit Primfaktoren
Die Phi-Funktion ist multiplikativ: Sind m und n teilerfremd, dann gilt \varphi(m\cdot n)=\varphi(m)\cdot\varphi(n). Zum Beispiel ist \varphi(18)=\varphi(2)\cdot\varphi(9)=1\cdot6=6.
Für eine Primzahlpotenz p^k, wobei k\in\mathbb N^+, sind genau die p^{k-1} Vielfachen von p im Bereich von 1 bis p^k nicht teilerfremd zu p^k. Deshalb: \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k\left(1-\frac1p\right). So ist \varphi(16)=\varphi(2^4)=8.
Hat n die kanonische Primfaktorzerlegung n=\prod_{p\mid n}p^{k_p}, dann folgt aus Multiplikativität und der Formel für Primzahlpotenzen: \varphi(n)=\prod_{p\mid n}p^{k_p-1}(p-1)=n\prod_{p\mid n}\left(1-\frac1p\right). Dabei laufen die Produkte über alle Primzahlen p, die n teilen. Für 72=2^3\cdot3^2 ergibt sich etwa \varphi(72)=72\left(1-\frac12\right)\left(1-\frac13\right)=24.
Wichtige Eigenschaften und Beziehungen
\varphi(n) ist die Anzahl der Einheiten im Restklassenring \mathbb Z/n\mathbb Z, also der Restklassen, die ein multiplikatives Inverses besitzen. Eine Restklasse \overline a ist genau dann eine Einheit, wenn a und n teilerfremd sind.
Für n>2 ist \varphi(n) immer gerade. Das Bild der Phi-Funktion, also die Menge ihrer Funktionswerte, hat natürliche Dichte 0: Wenn a_n die Anzahl der Funktionswerte höchstens n bezeichnet, gilt \lim_{n\to\infty}\frac{a_n}{n}=0.
Weitere Formeln sind: \varphi(n)>\frac{\sqrt n}{2};\qquad \text{für ungerades }n\text{ sogar }\varphi(n)\ge\sqrt n. Für n\ge2 gilt: \sum_{\substack{1\le j\le n-1\\\operatorname{ggT}(n,j)=1}}j=\frac n2\varphi(n). Für jedes n\in\mathbb N^+ gilt die Teilersummenformel: \sum_{\substack{d>0\\d\mid n}}\varphi(d)=n. Für n=100 liefern die Teiler 1,2,4,5,10,20,25,50,100 entsprechend die Phi-Werte 1,1,2,4,4,8,20,20,40; ihre Summe ist 100.
Die durchschnittliche Größenordnung von \varphi(n) ist \frac6{\pi^2}n. Genauer: \sum_{n=1}^{N}\varphi(n)=\frac{3}{\pi^2}N^2+\mathcal O(N\log N). Die Dirichlet-erzeugende Funktion lautet \sum_{n=1}^{\infty}\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}. Außerdem ist \varphi(n) die diskrete Fourier-Transformation der Folge \operatorname{ggT}(k,n) an der Stelle 1; insbesondere: \varphi(n)=\sum_{k=1}^{n}\operatorname{ggT}(k,n)\cos\left(2\pi\frac{k}{n}\right).
Bedeutung und Anwendungen
Eine zentrale Anwendung ist der Satz von Fermat-Euler. Sind die natürlichen Zahlen a und m teilerfremd, dann gilt \operatorname{ggT}(a,m)=1\Rightarrow m\mid a^{\varphi(m)}-1, also gleichbedeutend \operatorname{ggT}(a,m)=1\Rightarrow a^{\varphi(m)}\equiv1\pmod m. Für eine Primzahl p ist dies der kleine fermatsche Satz: p\nmid a\Rightarrow a^{p-1}\equiv1\pmod p. Der Satz von Fermat-Euler wird unter anderem beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie verwendet.
Die Phi-Funktion entscheidet auch über die Konstruierbarkeit regulärer Vielecke mit Zirkel und Lineal: Ein reguläres n-Eck ist genau dann konstruierbar, wenn \varphi(n)=2^m mit m\in\mathbb N eine Zweierpotenz ist. Das ist genau dann der Fall, wenn n das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist. Beispielsweise ist \varphi(85)=\varphi(5)\cdot\varphi(17)=4\cdot16=64; daher ist das reguläre 85-Eck konstruierbar.
