Eulersche φ-Funktion

23. Nov 2008, 17:57

Die ersten tausend Werte von $\varphi(n)$

Die eulersche $\varphi$ -Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl $n$ an, wie viele positive ganze Zahlen $a \le n$ zu ihr teilerfremd sind:

$\varphi(n) \; := \; \Big| \{ 1 \le a \le n \, |\, \operatorname{ggT}(a,n) = 1 \} \Big|$

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

Die $\varphi$ -Funktion ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben $\varphi$ (phi) bezeichnet.

Inhaltsverzeichnis

1 Beispiele
2 Eigenschaften
- 2.1 Multiplikative Funktion
- 2.2 Dichte
3 Berechnung
4 Bedeutung der -Funktion
5 Weblinks

[Bearbeiten] Beispiele

Die Zahl 6 ist zu zwei der Zahlen von 1 bis 6 teilerfremd (1 und 5), also ist $\varphi(6) = 2$ .
Die Zahl 13 ist als Primzahl zu den zwölf Zahlen 1 bis 12 teilerfremd, also ist $\varphi$ (13) = 12.
Die ersten zehn Werte der $\varphi$ -Funktion lauten:

n	1	2	3	4	5	6	7	8	9	10
teilerfremde Reste	1	1	1, 2	1, 3	1, 2, 3, 4	1, 5	1, 2, 3, 4, 5, 6	1, 3, 5, 7	1, 2, 4, 5, 7, 8	1, 3, 7, 9
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4

[Bearbeiten] Eigenschaften

[Bearbeiten] Multiplikative Funktion

Die $\varphi$ -Funktion ist eine multiplikative zahlentheoretische Funktion. Das heißt, dass für teilerfremde Zahlen $m$ und $n$ die Gleichung

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

gilt. Beispielsweise ist

$\varphi(18) = \varphi(2)\cdot\varphi(9) = 1\cdot 6 = 6$ .

[Bearbeiten] Dichte

$\varphi(n)\,$ gibt die Anzahl der Einheiten im Restklassenring $\Bbb{Z}/n\Bbb{Z}$ an.

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$ und $ab+nx=1\,$ ist, wenn man $x\in\Bbb{Z}$ geeignet wählt.

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 aus dem Bild $\mathrm{im}(\varphi)$ , die kleinergleich $n$ sind, dann gilt $\lim_{n\to\infty} \frac{a_n}{n}=0$ .

Das Bild der $\varphi$ -Funktion besitzt also natürliche Dichte 0.

[Bearbeiten] Berechnung

[Bearbeiten] Primzahlen

Da jede Primzahl $p$ nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis $p - 1$ teilerfremd. Es gilt daher

$\varphi(p) = p-1$

[Bearbeiten] Potenz von Primzahlen

Eine Potenz $p k$ mit einer Primzahl $p$ als Basis und einer natürlichen Zahl $k$ als Exponent hat mit $p$ nur einen Primfaktor. Infolgedessen hat $p k$ nur mit Vielfachen von $p$ einen von eins 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 die Formel

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

[Bearbeiten] Allgemeine Berechnungsformel

Der Wert der eulerschen $\varphi$ -Funktion lässt sich für jede Zahl aus ihrer kanonischen 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)$

Diese Formel folgt direkt aus der Multiplikativität der $\varphi$ -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$

[Bearbeiten] 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 O das Landau-Symbol ist.

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

[Bearbeiten] Bedeutung der $\varphi$ -Funktion

Eine der wichtigsten Anwendungen findet die $\varphi$ -Funktion im Satz von Fermat-Euler:

Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind, gilt:

$m \mid a^{\varphi(m)}-1$ (m teilt a hoch Phi von m minus 1),

oder anders formuliert:

$a^{\varphi(m)} \equiv 1 \pmod m$

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

$p \mid a^{p-1}-1$ ,

bzw.

$a^{p-1} \equiv 1 \pmod p$

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

[Bearbeiten] Weblinks

Die ersten 10000 Werte der $\varphi$ -Funktion
Programme zur $\varphi$ -Funktion
Folge der Funktionswerte $\varphi$ (n): Folge A000010 in OEIS

Von „http://de.wikipedia.org/wiki/Eulersche_%CF%86-Funktion“

Kategorie: Zahlentheorie

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Nützliche Listen

Abkürzungen • Dateiendungen • Netzjargon

Urheberrecht

Für alle Lexikon-Artikel gilt die GNU FDL (GNU Freie Dokumentationslizenz).
Die Wikipedia ist eine Enzyklopädie, deren Inhalte frei nutzbar sind und immer sein werden.

Eulersche φ-Funktion

Inhaltsverzeichnis

[Bearbeiten] Beispiele