Eulersche Phi-Funktion - LinkFang.de





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

[math]\varphi(n) \; := \; \Big| \{a\in\N \, |\, 1 \le a \le n \and \operatorname{ggT}(a,n) = 1 \} \Big|[/math]

Dabei bezeichnet [math]\operatorname{ggT}(a,n)[/math] den größten gemeinsamen Teiler von [math]a[/math] und [math]n.[/math] Außerdem wird hier und im ganzen weiteren Artikel unter der Menge [math]\N[/math] der natürlichen Zahlen die Menge der positiven ganzen Zahlen verstanden, sodass also stets [math]0\notin\N[/math] gilt.

Die Phi-Funktion ist benannt nach Leonhard Euler.

Beispiele

  • Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist [math]\!\ \varphi(6) = 2.[/math]
  • 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 [math]\!\ \varphi(13) = 12.[/math]

Die ersten 99 Werte der Phi-Funktion lauten:

[math]\varphi(n)[/math] +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 [math]m[/math] und [math]n[/math]

[math]\varphi (m \cdot n) = \varphi (m) \cdot \varphi (n)[/math]

gilt. Ein Beispiel dazu:

[math]\varphi(18) = \varphi(2)\cdot\varphi(9) = 1\cdot 6 = 6[/math]

Eigenschaften

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

Denn ist [math]\overline{a}\in\Bbb{Z}/n\Bbb{Z}[/math] eine Einheit, also [math]\overline{a}\in(\Bbb{Z}/n\Bbb{Z})^*,[/math] so gibt es ein [math]\overline{b}\in\Bbb{Z}/n\Bbb{Z}[/math] mit [math]\overline{a}\cdot\overline{b}=\overline{1},[/math] was äquivalent zu [math]ab\equiv 1 \, \mathrm{mod} \, n,[/math] also zur Existenz einer ganzen Zahl [math]x[/math] mit [math]ab+nx=1\,[/math] ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von [math]a\,[/math] und [math]n.[/math]

[math]\varphi(n)[/math] ist für [math]n\gt2[/math] stets eine gerade Zahl.

Ist [math]a_n[/math] die Anzahl der Elemente im Bild [math]\mathrm{im}(\varphi),[/math] die nicht größer als [math]n[/math] sind, dann gilt [math]\lim_{n\to\infty} \frac{a_n}{n}=0.[/math]

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 [math]\zeta[/math] zusammen:

[math] \sum_{n=1}^\infty \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}[/math]

Berechnung

Primzahlen

Da eine Primzahl [math]p[/math] nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis [math]p - 1[/math] teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

[math]\varphi(p) = p-1.[/math]

Potenz von Primzahlen

Eine Potenz [math]p^k[/math] mit einer Primzahl [math]p[/math] als Basis und einer natürlichen Zahl [math]k[/math] als Exponent hat nur den einen Primfaktor [math]p.[/math] Daher hat [math]p^k[/math] nur mit Vielfachen von [math]p[/math] einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis [math]p^k[/math] sind das die Zahlen

[math]1\cdot p,\;2\cdot p,\;3\cdot p,\;\cdots,\;p^{k-1}\cdot p = p^k.[/math]

Das sind [math]p^{k-1}[/math] Zahlen, die nicht teilerfremd zu [math]p^k[/math] sind. Für die eulersche [math]\!\ \varphi[/math]-Funktion gilt deshalb

[math]\varphi(p^k) = p^k-p^{k-1} = p^{k-1}(p-1)= p^{k}\left(1-\frac1{p}\right).[/math]

Beispiel:

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

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jede natürliche Zahl [math]n[/math] aus deren kanonischer Primfaktorzerlegung

[math]n = \prod_{p\mid n} p^{k_p}[/math]

berechnen:

[math]\varphi(n) = \prod_{p\mid n} p^{k_p-1}(p-1) = n \prod_{p\mid n}\left(1-\frac{1}{p}\right)[/math],

wobei die Produkte über alle Primzahlen [math]p[/math], die Teiler von [math]n[/math] sind, gebildet werden. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

Beispiel:

[math]\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[/math]

oder

[math]\varphi(72) = 72 \cdot (1 - \tfrac{1}{2}) \cdot (1 - \tfrac{1}{3}) = 24 [/math].

Abschätzung

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

[math]\sum_{n=1}^N \varphi(n) = \frac{1}{2 \zeta(2)} N^2 + \mathcal{O}(N \log N),[/math]

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

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

Fourier-Transformation

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

[math]\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}[/math]

Der Realteil davon ergibt die Gleichung

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

Weitere Beziehungen

  • Für [math]n \geq 2 [/math] gilt:
[math]\sum_{1 \leq j \leq n-1 \atop ggT(n,j)=1} j = \frac{n}{2} \varphi(n)[/math]
  • Für alle natürlichen Zahlen [math]n[/math] gilt:[2]
[math]\sum_{d \gt 0 \atop d | n} \varphi(d)= n[/math]
Beispiel: Für [math]n=100[/math] ist die Menge [math]T(n):=\{t\in\N: t|n\}[/math] der positiven Teiler von [math]n[/math] durch
[math]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\}[/math]
gegeben. Addition der zugehörigen [math]|T(100)| = (2+1)(2+1) = 9[/math] Gleichungen
[math]\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}[/math]
ergibt:
[math]\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 \gt 0 \atop d | 100} \varphi(d)&=100 \end{align}[/math]

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 [math]a^{\varphi(m)}-1:[/math]

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

Etwas anders formuliert:

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

Ein Spezialfall (für Primzahlen p) dieses Satzes ist der kleine fermatsche Satz:

[math]p \nmid a \Rightarrow p \mid a^{p-1}-1[/math]
[math]p \nmid a \Rightarrow a^{p-1} \equiv 1 \pmod p[/math]

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

Weblinks

Belege

  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.

Kategorien: Zahlentheoretische Funktion

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Eulersche Phi-Funktion (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.