Eulersche Phifunktion

Eulersche Phifunktion
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

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

Eigenschaften

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.

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 an 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.

Berechnung

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

Potenz von Primzahlen

Eine Potenz pk mit einer Primzahl p als Basis und einer natürlichen Zahl k als Exponent hat mit p nur einen Primfaktor. Infolgedessen hat pk nur mit Vielfachen von p einen von eins verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis pk sind das die Zahlen

1\cdot p, 2\cdot p, 3\cdot p, \cdots, p^{k-1} \cdot p = p^k

Das sind pk − 1 Zahlen, die nicht teilerfremd zu pk 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

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

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}.

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.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Phifunktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Euklidisches Lemma — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Primzahlen — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Dirichlets Theorem — Der dirichletsche Primzahlsatz (nach P. G. L. Dirichlet) ist eine Aussage aus dem mathematischen Teilgebiet der Zahlentheorie, der besagt, dass eine arithmetische Folge unendlich viele Primzahlen enthält, wenn dies nicht aus trivialen Gründen… …   Deutsch Wikipedia

  • Dirichletsches Theorem — Der dirichletsche Primzahlsatz (nach P. G. L. Dirichlet) ist eine Aussage aus dem mathematischen Teilgebiet der Zahlentheorie, der besagt, dass eine arithmetische Folge unendlich viele Primzahlen enthält, wenn dies nicht aus trivialen Gründen… …   Deutsch Wikipedia

  • Satz von Kronecker-Weber — Kreisteilungskörper sind Studienobjekte des mathematischen Teilgebietes der algebraischen Zahlentheorie. Sie sind in gewisser Hinsicht besonders einfache Verallgemeinerungen des Körpers der rationalen Zahlen. Definition: Es sei n > 2 eine… …   Deutsch Wikipedia

  • Zyklotomischer Körper — Kreisteilungskörper sind Studienobjekte des mathematischen Teilgebietes der algebraischen Zahlentheorie. Sie sind in gewisser Hinsicht besonders einfache Verallgemeinerungen des Körpers der rationalen Zahlen. Definition: Es sei n > 2 eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”