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 natürliche Zahl n an, wie viele zu n teilerfremde natürliche Zahlen es gibt, die nicht größer als n sind:

\varphi (n)\;:=\;{\Big |}\{a\in \mathbb{N} \,|\,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. Außerdem wird hier und im ganzen weiteren Artikel unter der Menge \mathbb {N} der natürlichen Zahlen die Menge der positiven ganzen Zahlen verstanden, sodass also stets 0\notin \mathbb{N} gilt.

Die Phi-Funktion ist benannt nach Leonhard Euler.

Beispiele

Die ersten 99 Werte der Phi-Funktion lauten:

\varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 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 jeder natürlichen Zahl n die Anzahl \varphi (n)\, der Einheiten im Restklassenring {\mathbb  {Z}}/n{\mathbb  {Z}} zu, also dieOrdnung 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\,{\mathrm  {mod}}\,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 einer natürlichen Zahl k als Exponent 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,\;\cdots ,\;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  12}\right)=8

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jede natürliche Zahl n aus deren 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 .

Abschätzung

Eine Abschätzung für das arithmetische Mittel von \!\ \varphi (n) erhält man über die Formel

\sum _{{n=1}}^{N}\varphi (n)={\frac  {1}{2\zeta (2)}}N^{2}+{\mathcal  {O}}(N\log N),

wobei ζ die riemannsche Zetafunktion und {\mathcal {O}} das Landau-Symbol ist.

Das heißt: Im Mittel ist \varphi (n)\approx n{\frac  {3}{\pi ^{2}}}..

Fourier-Transformation

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

\begin{align}
  \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 \dots 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{align}

Der Realteil davon ergibt die Gleichung

\varphi (n)=\sum\limits_{k=1}^n \operatorname{ggT}(k,n) \cos({2\pi\frac{k}{n})}.

Weitere Beziehungen

\sum _{{1\leq j\leq n-1 \atop ggT(n,j)=1}}j={\frac  {n}{2}}\varphi (n)
\sum_{d > 0 \atop d | n} \varphi(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: 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{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:
\begin{align} \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\\ \sum_{d > 0 \atop d | 100} \varphi(d)&=100 \end{align}

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

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

Etwas anders formuliert:

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

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 1{\pmod  p}

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

Trenner
Basierend auf einem Artikel in: externer Link Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 15.09. 2019