Eulersche φ-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 (also ggT(a,n) = 1).Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben φ (Phi) bezeichnet.
Table of contents |
2 Berechnung 3 Bedeutung der φ-Funktion: 4 Weblinks |
Beispiele
Die Zahl 6 ist zu 2 Zahlen zwischen 1 und 6 teilerfremd (1 und 5), also ist φ(6) = 2.
Die Zahl 13 ist als Primzahl zu den 12 Zahlen von 1 bis 12 teilerfremd, also ist φ(13) = 12.
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 |
Eine Zahl pα (wobei p ein Primzahl und α ≥ 1 ist) ist nur zu Vielfachen von p nicht teilerfremd. Es gibt pα-1 Vielfache von p, die kleiner oder gleich pα sind (1*p, 2*p, ..., pα-1*p), daher gilt:
Die φ-Funktion ist multiplikativ, das heißt für ggt(m,n) = 1 gilt:
Die Berechnung von φ(n) für zusammengesetzte n ergibt sich aus der Multiplikativität. Hat n die kanonische Darstellung
Eine der wichtigsten Anwendungen findet die φ-Funktion im Satz von Fermat-Euler:
Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind gilt: m teilt (aφ(m) - 1), oder anders formuliert:
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 φ(p) = p-1Potenzen von Primzahlen
Beispiel: φ(16) = φ( 24) = 24 - 23 = 16 - 8 = 8, bzw.: φ(16) = φ(24) = 23 * (2 - 1) = 8 * 1 = 8.Multiplikativität
Beispiel: φ(18) = φ(2) * φ(9) = 1 * 6 = 6.Zusammengesetzte Zahlen
so gilt
Beispiel: φ(72) = φ(2³*3²) = 23-1(2-1) * 32-1(3-1) = 2² * 1 * 3 * 2 = 24.
Bedeutung der φ-Funktion:
Ein Spezialfall (für m ist Primzahl) dieses Satzes ist der Kleine Fermatsche Satz: p teilt (ap-1 - 1), bzw.
Der Satz von Fermat-Euler findet u.a. Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahren in der Kryptographie.