Multiplikativität und Berechnungsformel

Mit Hilfe von Restsystemen können wir nun eine nicht offensichtliche Eigenschaft der Eulerschen φ-Funktion beweisen:

Satz (Multiplikativität der φ-Funktion)

Seien m₁, m₂ ≥ 1 teilerfremd. Dann gilt

φ(m₁ m₂) = φ(m₁) φ(m₂).(Multiplikativität der φ-Funktion)

Genauer sind

A = { r m₂ + s m₁ | r = 1, …, m₁; s = 1, …, m₂ }

B = { r m₂ + s m₁  ∈  A | (r, m₁) = 1, (s, m₂) = 1 }

ein Restsystem bzw. ein reduziertes Restsystem modulo m = m₁ m₂.

Die Voraussetzung der Teilerfremdheit ist wesentlich. Es gilt zum Beispiel φ(4) = 2 ≠ 1 = φ(2) φ(2).

Beweis

Aus (m₁, m₂) = 1 erhalten wir, dass für alle r, r′, s, s′ gilt (Übung):

(a)	r m₂ + s m₁ ≡ r′ m₂ + s′ m₁ (m) genau dann, wenn r ≡ r′ (m₁), s ≡ s′ (m₂).

(b)	(r m₂ + s m₁, m) = 1 genau dann, wenn (r, m₁) = (s, m₂) = 1.

Speziell gilt |A| = m und |B| = φ(m₁)φ(m₂). Nach (a) ist A ein Restsystem modulo m, und nach (b) gilt

B = { a  ∈  A | (a, m) = 1 }.

Damit ist B ein reduziertes Restsystem modulo m.

Der Beweis erlaubt es, die teilerfremden Reste modulo m aus den teilerfremden Resten der Faktoren m₁ und m₂ zu generieren:

Beispiele

(1)

Seien m₁ = 3 und m₂ = 10. Dann gilt m = 30, φ(m₁) = 2, φ(m₂) = 4,

r₁ = 1, r₂ = 2, s₁ = 1, s₂ = 3, s₃ = 7, s₄ = 9,

B = { 1 · 10 + 1 · 3, …, 2 · 10 + 9 · 3 } = { 13, 19, 31, 37, 23, 29, 41, 47 }.

Übergang zu kongruenten Zahlen im Intervall 1, …, 30 liefert

C = { 13, 19, 1, 7, 23, 29, 11, 17 } = { 1, 7, 11, 13, 17, 19, 23, 29 }.

Die acht Elemente von C sind die teilerfremden Reste modulo 30.

(2)	Seien nun n = 2 · 7 = 14 und m = 3 · 5 = 15, sodass nm = 210. Es gilt φ(14) = 6, φ(15) = 8, φ(210) = 6 · 8 = 48. In der folgenden Tabelle sind alle Werte rm + sn modulo mn eingetragen (eine Permutation der Zahlen 0, …, 209). Rot markiert sind die 48 zu 210 teilerfremden Zahlen.

Die Multiplikativität von φ lässt sich auch elegant mit Hilfe des Chinesischen Restsatzes beweisen:

Beweis der Multiplikativität mit Hilfe des Chinesischen Restsatzes

Da m₁ und m₂ teilerfremd sind, haben die Kongruenzen

x ≡ r (m₁) und x ≡ s (m₂)

für alle 1 ≤ r ≤ m₁ und 1 ≤ s ≤ m₂ genau eine gemeinsame Lösung x mit 1 ≤ x ≤ m. Verschiedene Paare (r, s), (r′, s′) führen zu verschiedenen Lösungen x, x′. Weiter gilt

(x, m) = 1 genau dann, wenn (r, m₁) = 1 und (s, m₂) = 1.

Dies zeigt, dass φ(m) = φ(m₁) φ(m₂).

Ohne weitere Schwierigkeiten erhalten wir nun eine Formel, die eine einfache Berechnung von φ(m) erlaubt, wenn die Primteiler von m bekannt sind:

Satz (Berechnungsformel für die φ-Funktion)

Sei m = p₁^e₁ … p_n^e_n die Primfaktorzerlegung von m ≥ 2. Dann gilt

φ(m) = ∏_{1 ≤ k ≤ n} (p_k^e_k − p_k^{e_k − 1}) = m ∏_{p prim, p | m} (1 − 1/p).

Beweis

Für alle Primzahlen p und alle e ≥ 1 gilt φ(p^e) = p^e − p^e − 1, da im Intervall von 1 bis p^e genau die p^e − 1 Zahlen

p, 2p, 3p, …, p^e − 1p

nicht teilerfremd zu p sind. Damit folgt die erste Formel aus der Multiplikativität von φ (da p_i^e_i und p_j^e_j für i ≠ j teilerfremd sind). Die zweite Formel erhalten wir durch Ausklammern der Faktoren p_k^e_k aus der ersten.

Beispiele

(1)	Es gilt 4400 = 2⁴ · 5² · 11. Damit erhalten wir φ(4400) = 4400 (1 − 1/2) (1 − 1/5) (1 − 1/11) = 4400 ^{1 · 4 · 10}_{2 · 5 · 11} = 1600.

(2)	Für p prim und k ≥ 1 gilt φ(p^k) = p^k (1 − 1/p) = (p − 1) p^k − 1. Speziell ist φ(2^k) = 2^k − 1, φ(3^k) = 2 · 3^k − 1, φ(5^k) = 4 · 5^k − 1.

(3)	Sind p ≠ q Primzahlen, so gilt φ(pq) = (p − 1) (q − 1).

Die Multiplikativität erklärt die Muster der φ-Funktion. Für p ≥ 5 prim gilt:

φ(p) = p − 1 ∼ p (gelb), φ(2p) = φ(p) ∼ (2p)/2 (grün), φ(3p) = 2φ(p) ∼ 3/2(3p) (rot)