Eulersche Phi-Funktion

Die ersten tausend Werte der 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 natürliche Zahlen es gibt, die nicht größer als $n$ sind (auch als Totient von $n$ bezeichnet).

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

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

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 Schreibweise ist die Darstellung als Summe:

$\varphi (n)\;=\;\sum \limits _{\overset {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$

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:

$\varphi (n)=\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. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |T(100)| = (2+1)(2+1) = 9} Gleichungen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \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{align}}

ergibt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \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{align}}

Bedeutung

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

Wenn zwei natürliche Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} teilerfremd sind, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ein Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^{\varphi(m)} - 1 \colon}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(a,m) = 1 \Rightarrow m \mid a^{\varphi(m)} - 1}

Etwas anders formuliert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(a,m) = 1 \Rightarrow a^{\varphi(m)} \equiv 1 \bmod m}

Ein Spezialfall (für Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} ) dieses Satzes ist der kleine fermatsche Satz:

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Die Phi-Funktion kommt auch in dem Kriterium für die Konstruierbarkeit eines Polygons vor.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi} and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.