Eulersche Phi-Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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\N \, |\, 1 \le a \le n \and \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 \N der natürlichen Zahlen die Menge der positiven ganzen Zahlen verstanden, sodass also stets 0\notin\N gilt.

Die Phi-Funktion ist benannt nach Leonhard Euler.

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • 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
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[Bearbeiten | Quelltext bearbeiten]

Multiplikative Funktion[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Die Funktion \varphi\, ordnet jeder natürlichen Zahl n die Anzahl \varphi(n)\, der Einheiten im Restklassenring \Bbb{Z}/n\Bbb{Z} zu, also die Ordnung der primen Restklassengruppe.

Denn ist \overline{a}\in\Bbb{Z}/n\Bbb{Z} eine Einheit, also \overline{a}\in(\Bbb{Z}/n\Bbb{Z})^*, so gibt es ein \overline{b}\in\Bbb{Z}/n\Bbb{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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Primzahlen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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-\frac1{p}\right).

Beispiel:

\varphi(16)=\varphi(2^4)=2^4-2^3=2^3\cdot (2-1)=2^4\cdot \left(1-\frac12\right) =8

Allgemeine Berechnungsformel[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:[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[Bearbeiten | Quelltext bearbeiten]

  • Für n \geq 2 gilt:
\sum_{1 \leq j \leq n-1 \atop ggT(n,j)=1} j = \frac{n}{2} \varphi(n)
  • Für alle natürlichen Zahlen n gilt:[2]
\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[Bearbeiten | Quelltext bearbeiten]

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.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Belege[Bearbeiten | Quelltext bearbeiten]

  1. Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: University of West Georgia, Karls-Universität Prag (Hrsg.): Integers Electronic Journal of Combinatorial Number Theory. 8, 2008, S. A50. Abgerufen am 24. Oktober 2015.
  2. Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.