Eulersche Phi-Funktion

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

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

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

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

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

• Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \varphi (13)=12.}$ 

Die ersten 99 Werte der Phi-Funktion lauten:

${\displaystyle \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

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

${\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)}$ 

gilt. Ein Beispiel dazu:

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

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

${\displaystyle \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.

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

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

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

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

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

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

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

${\displaystyle \varphi (p)=p-1.}$ 

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

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

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

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

Beispiel:

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

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

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

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

${\displaystyle \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 ${\displaystyle p}$ , die Teiler von ${\displaystyle n}$  sind, gebildet werden.

Beispiel:

${\displaystyle \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

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

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

${\displaystyle \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 ${\displaystyle \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:

${\displaystyle \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 ${\displaystyle \varphi (n)}$  ist ${\displaystyle {\tfrac {6}{\pi ^{2}}}n.}$ 

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

${\displaystyle {\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

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

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

• Für ${\displaystyle n\geq 2}$  gilt:

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

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

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

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

${\displaystyle 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 ${\displaystyle |T(100)|=(2+1)(2+1)=9}$  Gleichungen

${\displaystyle {\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:

${\displaystyle {\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}}}$ 

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

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

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

Etwas anders formuliert:

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

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

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

${\displaystyle 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 ${\displaystyle \varphi }$ -Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.

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

• Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
• Folge der Funktionswerte ${\displaystyle \varphi (n)\colon }$  Folge A000010 in OEIS
• Die ersten 100.000 Werte der Phi-Funktion (OEIS)
• Phi-Rechner (englisch)
• Florian Luca, Herman te Riele: ${\displaystyle \phi }$  and ${\displaystyle \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.

1. ↑ Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: Integers Electronic Journal of Combinatorial Number Theory. 8. Jahrgang. University of West Georgia, Karls-Universität Prag, 2008, S. A50 (colgate.edu [abgerufen am 31. Mai 2021]). 
2. ↑ Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.