Eulersche Phi-Funktion
Vorbemerkung: der Begriff Zahl bezieht sich in diesem Artikel stets auf natürliche Zahlen größer 0, also: 1, 2, 3, ...
Die Eulersche PHI-Funktion ( φ ) ordnet jeder Zahl n eine Zahl φ (n) = Anzahl der Zahlen von 1 bis n, die n nicht teilen zu.
Beispiel: die Zahl 6 wird von 2 Zahlen von 1 bis 6 nicht geteilt ( 4 und 5 ) -> φ (6) = 2. Beispiel: die Zahl 13 wird als Primzahl von den 12 Zahlen von 1 bis 12 nicht geteilt -> φ (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 |
allgemein gilt:
wenn die Zahl eine Primzahl p ist: &phi (p) = p - 1. wenn die Zahl eine Primzahlpotenz pn ist: &phi ( pn ) = pn - pn-1 = pn-1 * ( n - 1 ).
{ Beispiel: φ ( 16 )= &phi ( 24 ) = 24 - 23 = 16 - 8 = 8,
bzw.: φ ( 16 )= &phi ( 24 ) = 23 * ( 2 - 1 ) = 8 * 1 = 8. }
wenn die Zahlen a und b teilerfremd sind: φ ( a * b ) = φ ( a ) * φ ( b ).
{ Beispiel: φ ( 18 )= φ ( 2 ) * φ ( 9 ) = 1 * 6 = 6. }
Bedeutung der φ-Funktion:
Satz von Fermat-Euler:
wenn a und b teilerfremd sind gilt: b teilt ( a&phi(b) - 1 ).
Spezialfall ( b ist Primzahl ) ( Kleiner Fermatscher Satz ):
b teilt ( ab-1 - 1 ).
Der Satz von Fermat-Euler findet u.a. Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahhren