Eulersche φ-Funktion

aus Wikipedia, der freien Enzyklopädie

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 multiplikativ. Für teilerfremde Zahlen, das heißt Zahlen $m$ und $n$ mit $\operatorname{ggT}(m,n) = 1$ , gilt damit:

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

Beispiel:

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