Logo

Mathepedia

Unterstützen Sie die Mathepedia!

Jetzt

Mathepedia auf Facebook

Wurzelzieher Blog

Zahlentheorie


Eulersche Phi-Funktion

Die eulersche Phi-Funktion ist eine zahlentheoretische Funktion. Sie ordnet jeder natürlichen Zahl n die Anzahl der natürlichen Zahlen a von 1 bis n zu, die zu n teilerfremd sind, für die also ggT(a, n) = 1 ist.
Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben wFormel (Phi) bezeichnet.

Beispiele

  • Die Zahl 6 ist zu zwei Zahlen zwischen 1 und 6 teilerfremd (1 und 5), also ist wFormel(6) = 2.
  • Die Zahl 13 ist als Primzahl zu den zwölf Zahlen von 1 bis 12 teilerfremd, also ist wFormel(13) = 12.
  • Die ersten 20 Werte der wFormel-Funktion lauten:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
f(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8

Berechnung

Primzahlen

Da alle Primzahlen p nur durch 1 und sich selbst teilbar sind, sind sie sicher zu den Zahlen 1 bis p-1 teilerfremd, daher ist wFormel(p) = p-1.

Potenz von Primzahlen

Eine Potenz pk aus einer Primzahl p und einer natürlichen Zahl k ist nur zu Vielfachen von p nicht teilerfremd. Es gibt pk-1 Vielfache von p, die kleiner oder gleich pk sind (1*p, 2*p, ..., pk-1 *p). Daher gilt:
wFormel = pk-1 (p-1) = pk (1-1/p)
Beispiel
wFormel(16) = wFormel = 24 - 23 = 23 *(2 - 1) = 24 * (1-1/2) = 8 * 1 = 8

Multiplikativität

Die wFormel-Funktion ist multiplikativ für teilerfremde natürliche Zahlen:
wFormel, falls ggT(m, n) = 1
Beispiel:
wFormel(18) = wFormel(2)*wFormel(9) = 1*6 = 6
Gegenbeispiel für Zahlen m und n mit gemeinsamem Primfaktor:
wFormel(2*4) = wFormel(8) = 4, aber wFormel(2)*wFormel(4) = 1*2 = 2.

Zusammengesetzte Zahlen

Die Berechnung von wFormel(n) für zusammengesetzte Zahlen n ergibt sich aus der Multiplikativität. Hat n die kanonische Darstellung
wFormel (p ist Primzahl),
so gilt
wFormel
Beispiel
wFormel = 23-1 · (2-1) · 32-1 · (3-1) = 22 · 1 · 3 · 2 = 24

Abschätzung

Eine Abschätzung für das arithmetische Mittel von wFormel erhält man über die Formel
wFormel,
wobei wFormel die Riemannsche Zetafunktion und O das Landau-Symbol ist.
Das heißt: Im Mittel ist wFormel.

Man darf nicht das, was uns unwahrscheinlich und unnatürlich erscheint, mit dem verwechseln, was absolut unmöglich ist.

Carl Friedrich Gauß

 

 

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Eulersche Phi-Funktion aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Lizеnz Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). Listе dеr Autorеn des Originalartikels. Achtung! Unter Umständen besitzt diese Seite kaum noch Ähnlichkeit mit dem genannten Wιkιpеdιa-Artikel, da dieser komplett überarbeitet werdet musste, um Fehler und irrelevante Informationen zu entfernen.



Anbieterkеnnzeichnung: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 23.01.2014 12:41:37 (531 ms; 252 M)
C: 01.08.2014 07:44:28 (48 ms; 229 M)