Eulersche Phi-Funktion

Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede positive natürliche Zahl $n$ an, wie viele zu $n$ teilerfremde positive natürliche Zahlen es gibt, die nicht größer als $n$ sind (auch als Totient von $n$ bezeichnet).

Die ersten tausend Werte der Funktion

Ihr Funktionswert $\varphi (n)$ ist gleich der Anzahl der zu $n$ teilerfremden Reste modulo $n$. Für $n>1$ liegt er im Bereich $1\leq \varphi (n)<n$.

Der Name Phi-Funktion geht auf Leonhard Euler zurück.

Die Phi-Funktion entscheidet über die Konstruierbarkeit eines Polygons in Abhängigkeit von der Anzahl der Ecken des Vielecks $n$. Genau dann, wenn der Phi-Funktionswert $\varphi (n)$ von der Anzahl der Ecken $n$ des betroffenen Polygons eine Zweierpotenz $\varphi (n)=2^{m}\,\,{\text{mit}}\,\,\,m\in \mathbb {N}$ ist, ist das $n$-Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn $n$ das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

Definition

Die Phi-Funktion ist definiert durch $\varphi \colon \mathbb {N} ^{+}\to \mathbb {N} ^{+}$ und

$\varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,\mid \,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}{\Big |}$

Dabei bezeichnet $\operatorname {ggT} (a,n)$ den größten gemeinsamen Teiler von $a$ und $n.$

Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:

$\varphi (n)\;=\;\sum \limits _{\overset {1\leq a\leq n}{\operatorname {ggT} (a,n)=1}}1$

Beispiele

• Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist $\varphi (1)=1.$
• Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist $\varphi (6)=2.$
• Die Zahl 13 ist als Primzahl zu jeder der zwölf Zahlen von 1 bis 12 teilerfremd (aber natürlich nicht zu 13), also ist $\varphi (13)=12.$

Die ersten 99 Werte der Phi-Funktion lauten:

$\varphi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Eigenschaften

Multiplikative Funktion

Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen $m$ und $n$

$\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)$

gilt. Ein Beispiel dazu:

$\varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6$

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

$\varphi (85)=\varphi (5)\cdot \varphi (17)=4\cdot 16=64$

Das bedeutet, dass das reguläre 85-Eck sehr wohl mit Zirkel und Lineal konstruiert werden kann.

Denn der Phi-Funktionswert von der 85, also die 64 ist eine Zweierpotenz.

Eigenschaften

Die Funktion $\varphi \,$ ordnet jedem $n\in \mathbb {N} ^{+}$ die Anzahl $\varphi (n)\,$ der Einheiten im Restklassenring $\mathbb {Z} /n\mathbb {Z}$ zu, also die Ordnung der primen Restklassengruppe.

Denn ist ${\overline {a}}\in \mathbb {Z} /n\mathbb {Z}$ eine Einheit, also ${\overline {a}}\in (\mathbb {Z} /n\mathbb {Z} )^{*},$ so gibt es ein ${\overline {b}}\in \mathbb {Z} /n\mathbb {Z}$ mit ${\overline {a}}\cdot {\overline {b}}={\overline {1}},$ was äquivalent zu $ab\equiv 1{\bmod {n}},$ also zur Existenz einer ganzen Zahl $x$ mit $ab+nx=1\,$ ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von $a\,$ und $n.$

$\varphi (n)$ ist für $n>2$ stets eine gerade Zahl.

Ist $a_{n}$ die Anzahl der Elemente im Bild $\mathrm {im} (\varphi ),$ die nicht größer als $n$ sind, dann gilt $\lim _{n\to \infty }{\frac {a_{n}}{n}}=0.$ Das Bild der Phi-Funktion besitzt also die natürliche Dichte 0.

Erzeugende Funktion

Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion $\zeta$ zusammen:

$\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}$

Berechnung

Primzahlen

Da eine Primzahl $p$ nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis $p-1$ teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

$\varphi (p)=p-1.$

Potenz von Primzahlen

Eine Potenz $p^{k}$ mit einer Primzahl $p$ als Basis und dem Exponenten $k\in \mathbb {N} ^{+}$ hat nur den einen Primfaktor $p.$ Daher hat $p^{k}$ nur mit Vielfachen von $p$ einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis $p^{k}$ sind das die Zahlen

$1\cdot p,\;2\cdot p,\;3\cdot p,\;\dotsc ,\;p^{k-1}\cdot p=p^{k}$.

Das sind $p^{k-1}$ Zahlen, die nicht teilerfremd zu $p^{k}$ sind. Für die eulersche $\varphi$-Funktion gilt deshalb

$\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)$.

Beispiel:

$\varphi (16)=\varphi (2^{4})=2^{4}-2^{3}=2^{3}\cdot (2-1)=2^{4}\cdot \left(1-{\frac {1}{2}}\right)=8$.

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jedes $n\in \mathbb {N} ^{+}$ aus dessen kanonischer Primfaktorzerlegung

$n=\prod _{p\mid n}p^{k_{p}}$

berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:

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

wobei die Produkte über alle Primzahlen $p$, die Teiler von $n$ sind, gebildet werden.

Beispiel:

$\varphi (72)=\varphi (2^{3}\cdot 3^{2})=2^{3-1}\cdot (2-1)\cdot 3^{2-1}\cdot (3-1)=2^{2}\cdot 1\cdot 3\cdot 2=24$

oder

$\varphi (72)=72\cdot (1-{\tfrac {1}{2}})\cdot (1-{\tfrac {1}{3}})=24$.

Durchschnittliche Größenordnung

Mit der riemannschen Zetafunktion $\zeta$, dem Landau-Symbol ${\mathcal {O}}$ und $\zeta (2)={\tfrac {\pi ^{2}}{6}}$ gilt:

$\sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N)={\frac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N\log N)$

Wegen $\sum _{n=1}^{N}{\tfrac {6}{\pi ^{2}}}n={\tfrac {6}{\pi ^{2}}}{\tfrac {N(N+1)}{2}}={\tfrac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N)$ sind diese beiden Summen asymptotisch gleich:

$\lim _{N\to \infty }{\frac {\sum _{n=1}^{N}\varphi (n)}{\sum _{n=1}^{N}{\frac {6}{\pi ^{2}}}n}}=\lim _{N\to \infty }{\frac {{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log N}{N}}\right)}{{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {1}{N}}\right)}}=1$

Man sagt dazu auch:

• Die durchschnittliche Größenordnung von $\varphi (n)$ ist ${\tfrac {6}{\pi ^{2}}}n.$

Fourier-Transformation

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:

${\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{-2\pi i{\frac {mk}{n}}},\quad \mathbf {x_{k}} =\left\{\operatorname {ggT} (k,n)\right\}\quad {\text{für }}\,k\in \left\{1,\dotsc ,n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)e^{-2\pi i{\frac {k}{n}}}\end{aligned}}$

Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung

$\varphi (n)=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)\cos \left(2\pi {\frac {k}{n}}\right).$

Weitere Beziehungen

• Es gilt $\varphi (n)>{\frac {\sqrt {n}}{2}},$ für ungerade $n$ sogar $\varphi (n)\geq {\sqrt {n}}.$

• Für $n\geq 2$ gilt:

$\sum _{1\leq j\leq n-1 \atop \operatorname {ggT} (n,j)=1}j={\frac {n}{2}}\varphi (n)$

• Für alle $n\in \mathbb {N} ^{+}$ gilt:

$\sum _{d>0 \atop d\mid n}\varphi (d)=n$

Beispiel: Für $n=100$ ist die Menge $T(n):=\{t\in \ N^{+}\;{\big |}\;t\vert n\}$ der positiven Teiler von $n$ durch

$T(100)=T(2^{2}\cdot 5^{2})=\left\{2^{m}\cdot 5^{n}\mid m\in \{0,1,2\},n\in \{0,1,2\}\right\}=\{1,2,4,5,10,20,25,50,100\}$

gegeben. Addition der zugehörigen $|T(100)|=(2+1)(2+1)=9$ Gleichungen

${\begin{aligned}\varphi (1)&=1\\\varphi (2)&=1\\\varphi (4)&=2\\\varphi (5)&=4\\\varphi (10)&=4\\\varphi (20)&=8\\\varphi (25)&=20\\\varphi (50)&=20\\\varphi (100)&=40\end{aligned}}$

ergibt:

${\begin{aligned}\sum _{d>0 \atop d\mid 100}\varphi (d)&=\varphi (1)+\varphi (2)+\varphi (4)+\varphi (5)+\varphi (10)+\varphi (20)+\varphi (25)+\varphi (50)+\varphi (100)\\&=1+1+2+4+4+8+20+20+40=100\end{aligned}}$

Bedeutung

Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:

Wenn zwei natürliche Zahlen $a$ und $m$ teilerfremd sind, ist $m$ ein Teiler von $a^{\varphi (m)}-1\colon$

$\operatorname {ggT} (a,m)=1\Rightarrow m\mid a^{\varphi (m)}-1$

Etwas anders formuliert:

$\operatorname {ggT} (a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\bmod {m}}$

Ein Spezialfall (für Primzahlen $p$) dieses Satzes ist der kleine fermatsche Satz:

$p\nmid a\Rightarrow p\mid a^{p-1}-1$

$p\nmid a\Rightarrow a^{p-1}\equiv 1{\bmod {p}}$

Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Der $\varphi$-Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.

Siehe auch

• Hochkototiente Zahl
• Hochtotiente Zahl
• Nichtkototient
• Nichttotient
• Perfekt totiente Zahl
• Spärlich totiente Zahl
• Carmichaels Totientenfunktions-Vermutung

Weblinks

• Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
• Folge der Funktionswerte $\varphi (n)\colon$ Folge A000010 in OEIS
• Die ersten 100.000 Werte der Phi-Funktion (OEIS)
• Phi-Rechner (englisch)
• Florian Luca, Herman te Riele: $\phi$ and $\sigma$: from Euler to Erdös. Nieuw Archief voor Wiskunde, März 2011 (PDF; 304 kB).
• Video: Die Eulersche Phi-Funktion. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19894.