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 ${\displaystyle n}$ an, wie viele zu ${\displaystyle n}$ teilerfremde positive natürliche Zahlen es gibt, die nicht größer als ${\displaystyle n}$ sind (auch als Totient von ${\displaystyle n}$ bezeichnet).

Ihr Funktionswert ${\displaystyle \varphi (n)}$ ist gleich der Anzahl der zu ${\displaystyle n}$ teilerfremden Reste modulo ${\displaystyle n}$. Für ${\displaystyle n>1}$ liegt er im Bereich ${\displaystyle 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 ${\displaystyle n}$. Genau dann, wenn der Phi-Funktionswert ${\displaystyle \varphi (n)}$ von der Anzahl der Ecken ${\displaystyle n}$ des betroffenen Polygons eine Zweierpotenz ${\displaystyle \varphi (n)=2^{m}\,\,{\text{mit}}\,\,\,m\in \mathbb {N} }$ ist, ist das ${\displaystyle n}$-Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn ${\displaystyle n}$ das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

Definition

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

Beispiele

• 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

Eigenschaften

Multiplikative 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.

Eigenschaften

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.

Erzeugende Funktion

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

Berechnung

Primzahlen

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

Potenz von Primzahlen

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

Allgemeine Berechnungsformel

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

Durchschnittliche Größenordnung

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

Fourier-Transformation

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

Weitere Beziehungen

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

Bedeutung

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.

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

Einzelnachweise

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.