Euler’sche φ-Funktion

Euler’sche φ-Funktion
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:

  • Euler'sche Zahl — Die eulersche Zahl e = 2,718281828459... (nach dem Schweizer Mathematiker Leonhard Euler) ist eine irrationale und sogar transzendente reelle Zahl. Die eulersche Zahl ist die Basis des natürlichen Logarithmus und der (natürlichen)… …   Deutsch Wikipedia

  • Euler'sche Identität — Veranschaulichung in der komplexen Zahlenebene Die eulersche Identität bezeichnet die Formel und bildet das Bindeglied zwischen trigonometrischen Funktionen und den komplexen Zahlen. Dabei bezeichnet …   Deutsch Wikipedia

  • Barnes'sche G-Funktion — Die Barnessche G Funktion, typischerweise mit G(z) bezeichnet, ist eine Funktion, die eine Erweiterung der Superfakultäten auf die komplexen Zahlen darstellt. Sie steht in Beziehung zur Gammafunktion, der K Funktion und der Konstanten von… …   Deutsch Wikipedia

  • Lagrange-Funktion — Die Lagrange Funktion (nach Joseph Louis Lagrange) ist ein zentrales Element zur Beschreibung von physikalischen Systemen im Lagrange Formalismus der Klassischen Mechanik. Für konservative Systeme sowie für nicht konservative Systeme mit einem… …   Deutsch Wikipedia

  • Weierstraßsche elliptische Funktion — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die keine reellen Vielfachen voneinander sind, so dass …   Deutsch Wikipedia

  • Weierstraßsche p-Funktion — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die keine reellen Vielfachen voneinander sind, so dass …   Deutsch Wikipedia

  • Elliptische Funktion — Im mathematischen Teilgebiet der Funktionentheorie sind elliptische Funktionen doppeltperiodische meromorphe Funktionen. „Doppeltperiodisch“ bedeutet, dass es zwei komplexe Zahlen ω1,ω2 gibt, die linear unabhängig im reellen Vektorraum sind, so… …   Deutsch Wikipedia

  • Exponentialfunktion — Funktion, die dadurch gekennzeichnet ist, dass die unabhängige Variable im Exponenten steht. Allgemein hat eine E. die Funktionsform:f(x) = ax (a > 0).Die wichtigste E. in der Wirtschaft ist die e Funktion:f(x) = ex (e: ⇡ Euler sche Zahl).E.… …   Lexikon der Economics

  • Sinus und Kosinus — Graphen der Sinusfunktion (rot) und der Kosinusfunktion (blau). Beide Funktionen sind 2π periodisch und nehmen Werte von −1 bis 1 an. Sinus und Kosinusfunktion (auch Cosinusfunktion) sind elementare mathematische Funktionen. Vor Tangens und… …   Deutsch Wikipedia

  • Geheimidentität — Beim Menschen bezeichnet Identität (v. lat. idem, derselbe, der gleiche) die ihn kennzeichnende und als Individuum von anderen Menschen unterscheidende Eigentümlichkeit seines Wesens. Analog wird der Begriff auch zur Charakterisierung von… …   Deutsch Wikipedia

Share the article and excerpts

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