Hauptmenü öffnen

Eulersche Phi-Funktion

mathematische Funktion
Die ersten tausend Werte der Funktion

Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede positive natürliche Zahl an, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind (auch als Totient von bezeichnet):

Dabei bezeichnet den größten gemeinsamen Teiler von und

Die Phi-Funktion ist benannt nach Leonhard Euler.

Inhaltsverzeichnis

BeispieleBearbeiten

  • Die Zahl 1 ist als Sonderfall des leeren Produkts (weder Primzahl noch zusammengesetzte Zahl) auch zu sich selber teilerfremd, also ist  
  • Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist  
  • Die Zahl 13 ist als Primzahl zu jeder der zwölf Zahlen von 1 bis 12 teilerfremd (aber natürlich nicht zu 13), also ist  

Die ersten 99 Werte der Phi-Funktion lauten:

  +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
00+   01 01 02 02 04 02 06 04 06
10+ 04 10 04 12 06 08 08 16 06 18
20+ 08 12 10 22 08 20 12 18 12 28
30+ 08 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

EigenschaftenBearbeiten

Multiplikative FunktionBearbeiten

Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen   und  

 

gilt. Ein Beispiel dazu:

 

EigenschaftenBearbeiten

Die Funktion   ordnet jedem   die Anzahl   der Einheiten im Restklassenring   zu, also die Ordnung der primen Restklassengruppe.

Denn ist   eine Einheit, also   so gibt es ein   mit   was äquivalent zu   also zur Existenz einer ganzen Zahl   mit   ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von   und  

  ist für   stets eine gerade Zahl.

Ist   die Anzahl der Elemente im Bild   die nicht größer als   sind, dann gilt  

Das Bild der Phi-Funktion besitzt also die natürliche Dichte 0.

Erzeugende FunktionBearbeiten

Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion   zusammen:

 

BerechnungBearbeiten

PrimzahlenBearbeiten

Da eine Primzahl   nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis   teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

 

Potenz von PrimzahlenBearbeiten

Eine Potenz   mit einer Primzahl   als Basis und dem Exponenten   hat nur den einen Primfaktor   Daher hat   nur mit Vielfachen von   einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis   sind das die Zahlen

 

Das sind   Zahlen, die nicht teilerfremd zu   sind. Für die eulersche  -Funktion gilt deshalb

 

Beispiel:

 

Allgemeine BerechnungsformelBearbeiten

Der Wert der eulerschen Phi-Funktion lässt sich für jedes   aus dessen kanonischer Primfaktorzerlegung

 

berechnen:

 ,

wobei die Produkte über alle Primzahlen  , die Teiler von   sind, gebildet werden. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

Beispiel:

 

oder

 .

Durchschnittliche GrößenordnungBearbeiten

Mit der riemannschen Zetafunktion  , dem Landau-Symbol   und   gilt:

 

Wegen   sind diese beiden Summen asymptotisch gleich:

 

Man sagt dazu auch:

Fourier-TransformationBearbeiten

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:[1]

 

Der Realteil davon ergibt die Gleichung

 

Weitere BeziehungenBearbeiten

  • Es gilt  , für ungerade   sogar  .
  • Für   gilt:
 
  • Für alle   gilt:[2]
 
Beispiel: Für   ist die Menge   der positiven Teiler von   durch
 
gegeben. Addition der zugehörigen   Gleichungen
 
ergibt:
 

BedeutungBearbeiten

Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:

Wenn zwei natürliche Zahlen   und   teilerfremd sind, ist   ein Teiler von  

 

Etwas anders formuliert:

 

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

 
 

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

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: University of West Georgia, Karls-Universität Prag (Hrsg.): Integers Electronic Journal of Combinatorial Number Theory. 8, 2008, S. A50. Abgerufen am 24. Oktober 2015.
  2. Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.