Eulersche Phi-Funktion

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}}}$