Eulersche Phi-Funktion

mathematische Funktion, gibt die Anzahl teilerfremder (koprimer) natürlicher Zahlen unterhalb von n an
(Weitergeleitet von Eulersche 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 positive natürliche Zahlen es gibt, die nicht größer als sind (auch als Totient von bezeichnet).

Die ersten tausend Werte der Funktion

Ihr Funktionswert ist gleich der Anzahl der zu teilerfremden Reste modulo . Für liegt er im Bereich .

Der Name Phi-Funktion geht auf Leonhard Euler zurück.

Die Phi-Funktion entscheidet über die Konstruierbarkeit eines Polygons in Abhängigkeit von der Anzahl der Ecken des Vielecks . Genau dann, wenn der Phi-Funktionswert von der Anzahl der Ecken des betroffenen Polygons eine Zweierpotenz ist, ist das -Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

Definition

Bearbeiten

Die Phi-Funktion ist definiert durch   und

 

Dabei bezeichnet   den größten gemeinsamen Teiler von   und  

Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:

 

Beispiele

Bearbeiten
  • Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, 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

Eigenschaften

Bearbeiten

Multiplikative Funktion

Bearbeiten

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

 

gilt. Ein Beispiel dazu:

 

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

 

Das bedeutet, dass das reguläre 85-Eck sehr wohl mit Zirkel und Lineal konstruiert werden kann.

Denn der Phi-Funktionswert von der 85, also die 64 ist eine Zweierpotenz.

Eigenschaften

Bearbeiten

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 Funktion

Bearbeiten

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

 

Berechnung

Bearbeiten

Primzahlen

Bearbeiten

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 Primzahlen

Bearbeiten

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 Berechnungsformel

Bearbeiten

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

 

berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:

 ,

wobei die Produkte über alle Primzahlen  , die Teiler von   sind, gebildet werden.

Beispiel:

 

oder

 .

Durchschnittliche Größenordnung

Bearbeiten

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

 

Wegen   sind diese beiden Summen asymptotisch gleich:

 

Man sagt dazu auch:

Fourier-Transformation

Bearbeiten

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

 

Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung

 

Weitere Beziehungen

Bearbeiten
  • 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:
 

Bedeutung

Bearbeiten

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.

Der  -Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.

Siehe auch

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: Integers Electronic Journal of Combinatorial Number Theory. 8. Jahrgang. University of West Georgia, Karls-Universität Prag, 2008, S. A50 (colgate.edu [abgerufen am 31. Mai 2021]).
  2. Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.