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

Ihr Funktionswert $\phi (n)$ ist gleich der Anzahl der zu $n$ teilerfremden Reste modulo $n$. Für $n>1$ liegt er im Bereich $1\le \phi (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 $\phi (n)$ von der Anzahl der Ecken $n$ des betroffenen Polygons eine Zweierpotenz $\phi (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 $\phi :{\mathbb{N}}^{+}\to {\mathbb{N}}^{+}$ und

$\phi (n):=|\{a\in \mathbb{N}\mid 1\le a\le n\wedge \mathrm{ggT}(a,n)=1\}|$

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

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

$\phi (n)=\sum _{\stackrel{1\le a\le n}{\mathrm{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 $\phi (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 $\phi (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 $\phi (13)=12.$

Die ersten 99 Werte der Phi-Funktion lauten:

$\phi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
Vorlage:00+		Vorlage:01	Vorlage:01	Vorlage:02	Vorlage:02	Vorlage:04	Vorlage:02	Vorlage:06	Vorlage:04	Vorlage:06
10+	Vorlage:04	10	Vorlage:04	12	Vorlage:06	Vorlage:08	Vorlage:08	16	Vorlage:06	18
20+	Vorlage:08	12	10	22	Vorlage:08	20	12	18	12	28
30+	Vorlage: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$

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

gilt. Ein Beispiel dazu:

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

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

$\phi (85)=\phi (5)\cdot \phi (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 $\phi$ ordnet jedem $n\in {\mathbb{N}}^{+}$ die Anzahl $\phi (n)$ der Einheiten im Restklassenring $\mathbb{Z}/n\mathbb{Z}$ zu, also die Ordnung der primen Restklassengruppe.

Denn ist $\bar{a}\in \mathbb{Z}/n\mathbb{Z}$ eine Einheit, also $\bar{a}\in (\mathbb{Z}/n\mathbb{Z}{)}^{*},$ so gibt es ein $\bar{b}\in \mathbb{Z}/n\mathbb{Z}$ mit $\bar{a}\cdot \bar{b}=\bar{1},$ was äquivalent zu $ab\equiv 1modn,$ 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.$

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

Ist $a_n$ die Anzahl der Elemente im Bild $\mathrm{i}\mathrm{m}(\phi ),$ die nicht größer als $n$ sind, dann gilt $\underset{n\to \mathrm{\infty }}{\lim }\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}^{\mathrm{\infty }}\frac{\phi (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

$\phi (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,\dots ,p^{k-1}\cdot p=p^k$.

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

$\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k(1-\frac{1}{p})$.

Beispiel:

$\phi (16)=\phi (2^4)=2^4-2^3=2^3\cdot (2-1)=2^4\cdot (1-\frac{1}{2})=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:

$\phi (n)=\prod _{p\mid n}\phi (p^{k_p})=\prod _{p\mid n}{p}^{k_p-1}(p-1)=n\prod _{p\mid n}(1-\frac{1}{p})$,

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

Beispiel:

$\phi (72)=\phi (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

$\phi (72)=72\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})=24$.

Durchschnittliche Größenordnung

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

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

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

$\underset{N\to \mathrm{\infty }}{\lim }\frac{\sum _{n=1}^N\phi (n)}{\sum _{n=1}^N\frac{6}{{\pi }^2}n}=\underset{N\to \mathrm{\infty }}{\lim }\frac{\frac{3}{{\pi }^2}+𝒪\left(\frac{\log N}{N}\right)}{\frac{3}{{\pi }^2}+𝒪\left(\frac{1}{N}\right)}=1$

Man sagt dazu auch:

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

Fourier-Transformation

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

$\begin{array}{cc}ℱ\left\{𝐱\right\}[m]& =\sum _{k=1}^n{x}_k\cdot e^{-2\pi i\frac{mk}{n}},{𝐱}_{𝐤}=\{\mathrm{ggT}(k,n)\}\text{für }k\in \{1,\dots ,n\}\\ \phi (n)& =ℱ\left\{𝐱\right\}[1]=\sum _{k=1}^n\mathrm{ggT}(k,n)e^{-2\pi i\frac{k}{n}}\end{array}$

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

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

Weitere Beziehungen

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

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

$\sum _{\genfrac{}{}{0ex}{}{1\le j\le n-1}{\mathrm{ggT}(n,j)=1}}j=\frac{n}{2}\phi (n)$

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

$\sum _{\genfrac{}{}{0ex}{}{d>0}{d\mid n}}\phi (d)=n$

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

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

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

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

ergibt:

$\begin{array}{cc}\sum _{\genfrac{}{}{0ex}{}{d>0}{d\mid 100}}\phi (d)& =\phi (1)+\phi (2)+\phi (4)+\phi (5)+\phi (10)+\phi (20)+\phi (25)+\phi (50)+\phi (100)\\ & =1+1+2+4+4+8+20+20+40=100\end{array}$

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^{\phi (m)}-1:$

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

Etwas anders formuliert:

$\mathrm{ggT}(a,m)=1\Rightarrow a^{\phi (m)}\equiv 1modm$

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 1modp$

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

Der $\phi$-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

• Vorlage:MathWorld
• Folge der Funktionswerte $\phi (n):$ Vorlage:OEIS
• Die ersten 100.000 Werte der Phi-Funktion (OEIS)
• Phi-Rechner (englisch)
• Florian Luca, Herman te Riele: $\varphi$ and $\sigma$: from Euler to Erdös. Nieuw Archief voor Wiskunde, März 2011 (PDF; 304 kB).
• Vorlage:TIBAV