| |
|
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.
{| border="1" cellspacing="1"
| 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) = &phi( 24) = 24 - 23 = 16 - 8 = 8, bzw.: φ(16) = &phi(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.