3. Die Anzahl teilerfremder Zahlen
Im Sieb des Eratosthenes ermitteln wir alle Primzahlen eines Intervalls. Eine natürliche „relative Variante“ ist es, alle zu einer gegebenen Zahl teilerfremden Zahlen zu ermitteln, also die relativen anstelle der absoluten Primzahlen. Wir betrachten hierzu ein festes m ≥ 1 und fragen nach den teilerfremden Zahlen im Intervall { 1, …, m }. Die Anzahl dieser Zahlen wird durch eine klassische Funktion der Zahlentheorie festgehalten:
Definition (Eulersche φ-Funktion)
Wir definieren φ : ℕ* → ℕ* durch
φ(m) = | { 1 ≤ n ≤ m | n und m sind relativ prim } | für alle m ≥ 1.
Die Funktion φ heißt die Eulersche φ-Funktion (gelesen: phi-Funktion).
Traditionell spielt die φ-Funktion beim Modulo-Rechnen eine große Rolle, weswegen der Buchstabe m gegenüber n bei der Funktionsanwendung bevorzugt wird.
Die folgende Tabelle gibt einen Überblick über die teilerfremden Zahlen und die Werte der φ-Funktion für m = 1, …, 10.
m | teilerfremde n mit 1 ≤ n ≤ m | φ(m) |
1 | 1 | 1 |
2 | 1 | 1 |
3 | 1, 2 | 2 |
4 | 1, 3 | 2 |
5 | 1, 2, 3, 4 | 4 |
6 | 1, 5 | 2 |
7 | 1, 2, 3, 4, 5, 6 | 6 |
8 | 1, 3, 5, 7 | 4 |
9 | 1, 2, 4, 5, 7, 8 | 6 |
10 | 1, 3, 7, 9 | 4 |
Ist p eine Primzahl, so gilt φ(p) = p − 1, da genau die Zahlen 1, …, p − 1 relativ prim zu p sind. Umgekehrt folgt aus φ(m) = m − 1, dass m eine Primzahl ist. Denn gilt φ(m)= m − 1, so ist m ≥ 2 und alle Zahlen 1, …, m − 1 sind relativ prim zu m, sodass m keine Teiler außer 1 und m besitzt. Die Primzahlen sind also die Zahlen mit maximalen φ-Werten − abgesehen vom Sonderfall φ(1) = 1.
Für Primzahlen p können wir φ(p) also leicht berechnen. Wie berechnen wir aber φ(m) im allgemeinen Fall? Das Werteverhalten von φ macht zunächst wenig Hoffnung auf eine einfache Antwort:
Verlauf der φ-Funktion bis m = 300
Der Verlauf ist sprunghaft, zeigt aber ein gewisses Wachstum. Deutlich erkennbar sind die Primzahlen mit φ-Werten knapp unterhalb der Hauptdiagonalen. Weitere Linien lassen sich erkennen, insbesondere sehen wir viele Werte in der Nähe der Geraden mit Steigung 1/2. Angesichts dieser Phänomene scheint eine einfache Berechnungsformel für φ vielleicht eher unwahrscheinlich zu sein. Dennoch gibt es eine solche Formel und mit ihrer Hilfe werden wir in der Lage sein, viele Phänomene des Verlaufs der φ-Funktion zu erklären. Und sie zu finden, müssen wir lediglich unser Siebverfahren leicht anpassen:
Siebverfahren zur Bestimmung der teilerfremden Zahlen
Sei m ≥ 2, und seien p1 < … < pk die Primteiler von m. Wir erstellen eine Tabelle aller Zahlen 1, …, m und streichen in k Durchläufen die Vielfachen von p1, …, pk (einschließlich p1, …, pk).
Die Menge der zu m teilerfremden Zahlen im Zahlenintervall von 1 bis m besteht aus genau den Zahlen, die diese Siebung überleben. Um diese Menge zu zählen, müssen wir wieder Mehrfachstreichungen durch ein Einschluss-Ausschluss-Argument berücksichtigen. Zur Illustration betrachten wir zunächst den übersichtlichen Fall, dass m das Produkt zweier verschiedener Primzahlen p und q ist. Sieben wir mit p, so streichen wir m/p = q Zahlen. Sieben wir mit q, so streichen wir m/q = p Zahlen. Dabei haben wir die Vielfachen von p q doppelt gestrichen, in unserem Fall also genau die Zahl m = p q. Damit ergibt sich
φ(p q) = p q − q − p + 1 = (p − 1)(q − 1) = m (1 − 1/p) (1 − 1/q).
Allgemein erhalten wir:
Satz (Berechnungsformel für die φ-Funktion)
Sei m ≥ 1. Dann gilt
φ(m) = m ∏p|m (1 − 1/p).
Beweis
Seien p, q, … alle Primteiler von n. Bei der Siebung mit p werden n/p Zahlen gestrichen, bei der Siebung mit q werden n/q Zahlen gestrichen usw. Bei den Siebungen mit p und q werden n/(pq) Zahlen doppelt gestrichen. Das Gleiche gilt für alle anderen Primteilerpaare vom m. Durch eine Einschluss-Ausschluss-Argumentation mit Primteilern, Primteilerpaaren, Primteiltertripeln usw. erhalten wir
φ(m) = m − ∑p|m mp1 + ∑p,q|m mp q − …
Ausklammern von m ergibt
φ(m) = m (1 − ∑p|m 1p1 + ∑p,q|m 1p q − …).
Anwendung des Distributivgesetzes liefert
φ(m) = m ∏p|m (1 − 1p).
(Der Leser multipliziere den Term (1 − 1/2)(1 − 1/3)(1 − 1/5) aus, um sich die Wirkung des Distributivgesetzes für Faktoren dieser Form vor Augen zu führen.)
Wir können also den Funktionswert φ(m) einfach berechnen, wenn die Primteiler von m bekannt sind.
Beispiele
(1) | φ(90) = φ(2 · 32 · 5) = 90(1 − 1/2)(1 − 1/3)(1 − 1/5) = 90 · 4/15 = 24. |
(2) | Sind p ≠ q Primzahlen, so gilt φ(p q) = p q(1 − 1/p)(1 − 1/q) = (p − 1)(q − 1), in Übereinstimmung mit unserer Vorabüberlegung. |
(3) | Ist p prim und n ≥ 1, so gilt φ(pn) = pn(1 − 1/p) = pn − pn − 1. Dieses Ergebnis können wir auch leicht direkt beweisen, denn im Zahlenintervall von 1 bis pn sind genau die Zahlen p, 2p, …, ap mit a = pn − 1 sind nicht teilerfremd zu m, sodass φ(pn) = pn − a = pn − pn − 1. |
Aus dem Berechnungssatz ergibt sich:
Korollar (Multiplikativität von φ)
Seien m und n relativ prim. Dann gilt φ(m n) = φ(m) φ(n).
Beweis
Da m und n keine gemeinsamen Primteiler besitzen, gilt
| φ(mn) | = (m n) ∏p|mn (1 − 1/p) |
| = m ∏p|m (1 − 1/p) n ∏p|n (1 − 1/p) | |
| = φ(m) φ(n). |
Der Satz ist ein Paradebeispiel für die „gute Voraussetzung“ der Teilerfremdheit. Es gilt zum Beispiel
φ(12) = φ(3 · 4) = φ(3) · φ(4) = 2 · 2 = 4, aber
φ(2) · φ(6) = 1 · 2 = 2 ≠ φ(12).
Mit Hilfe unserer Ergebnisse können wir nun viele Phänomene des obigen Graphen der φ-Funktion erklären:
(1) | Wachstum der Funktion Die Berechnungsformel der φ-Funktion in der Form φ(m) = m ∏p|m ((p − 1)/p) zeigt, dass φ(m) ein gewisser nicht allzu kleiner Anteil von m ist. Dieser Anteil ist von den unregelmäßig verteilten Primteilern von m abhängig. |
(2) | Linienmuster Die Multiplikativität φ(nm) = φ(n)φ(m) für teilerfremde Zahlen n, m führt zu den Linienmustern. Zum Beispiel gilt φ(2p) = φ(2) φ(p) = p − 1 für alle Primzahlen p ≥ 3. Da p − 1 in etwa so groß ist wie die Hälfte von 2p, entsteht in graphischen Darstellungen ein Linienmuster mit der Steigung 1/2. Analoges gilt für φ(3p) usw. |
Anpassung der Einschluss-Ausschluss-Darstellung der Eins
In noch größerer Analogie zu unseren früheren Überlegungen können wir den Berechnungssatz auch so beweisen: Sieben wir in einem Intervall { 1, …, m } mit allen Primzahlen kleinergleich m, so gilt
m = 1 + ∑p1 < … < pk ≤ m (−1)k − 1 ⌊mp1 … pk⌋
nach unserer Einschluss-Ausschluss-Darstellung einer Zahl. Sieben wir lediglich mit den Primteilern von m, so verändern sich in dieser Formel zwei Dinge: Zum einen überlebt nicht nur die 1, sondern es bleiben genau φ(m) Zahlen übrig. Denn genau die zu m teilerfremden Zahlen werden nicht markiert oder gestrichen. Zum anderen können wir in der Summe die Floor-Funktion weglassen, da alle Brüche ganzzahlig sind. Damit erhalten wir
(+) m = φ(m) + ∑p1, …, pk|m (−1)k − 1 mp1 … pk
mit paarweise verschiedenen Primteilern in der Summe. Durch Subtraktion der Summe auf beiden Seiten, Ausklammern von m und Anwendung des Distributivgesetzes erhalten wir erneut die obige Berechnungsformel.
Verwendung der Möbius-Funktion
Wie früher können wir auch wieder die Möbius-Funktion verwenden, um unser Ergebnis in kompakter Form zu notieren:
Satz (φ-Funktion und Möbius-Funktion)
Sei m ≥ 1. Dann gilt
φ(m) = m ∑d|m μ(d)/d.
Beweis
Aus (+) ergibt sich
| φ(m) | = m − ∑p1, …, pk|m (−1)k − 1 mp1 … pk |
| = m + ∑p1, …, pk|m (−1)k mp1 … pk | |
| = μ(1) m/1 + ∑p1, …, pk|m μ(p1 … pk) mp1 … pk | |
| = ∑d|m μ(d) m/d = m ∑d|m μ(d)/d. |
Im vorletzten Schritt verwenden wir, dass φ(d) = 0 für alle Teiler d von m gilt, die einen Primfaktor vom m mehrfach enthalten.