Die φ-Funktion

Die Kürzungsregel zeigt, dass die zu einem Modul m teilerfremden Zahlen gute Eigenschaften besitzen. Modulo m können wir diese Zahlen immer zwischen 1 und m wählen. Die folgende Funktion zählt, wie viele derartige Zahlen es in Abhängigkeit des Moduls gibt:

Definition (Eulersche φ-Funktion)

Wir definieren φ : ℕ* → ℕ* durch

φ(m) =  | { n | 1 ≤ n ≤ m und (n, m) = 1 } |  für alle m ≥ 1.

Die Funktion φ heißt die Eulersche φ-Funktion.

Hier und im Folgenden bezeichnet |A| die Anzahl der Elemente einer endlichen Menge A. Nach Definition gilt φ(1) = 1. Für alle m ≥ 2 ist φ(m) die Anzahl der zu m teilerfremden Zahlen r mit 1 ≤ r < m. Wir erläutern die Definition durch einige Beispiele.

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
11	1, …, 10	10
12	1, 5, 7, 11	4
13	1, …, 12	12
14	1, 3, 5, 9, 11, 13	6
15	1, 2, 4, 7, 8, 11, 13, 14	8
16	1, 3, 5, 7, 9, 11, 13, 15	8
17	1, …, 16	16
18	1, 5, 7, 11, 13, 17	6
19	1, …, 18	18
20	1, 3, 7, 9, 11, 13, 17, 19	8

Die Zahlen in der mittleren Spalte nennen wir auch die teilerfremden Reste modulo m, und wir zählen sie in der Form

1 = r₁ < … < r_φ(m) ≤ m

auf. (Diese Sprechweise ist für m = 1 streng genommen nicht korrekt, da die 1 kein Rest einer Division durch 1 ist.) Für m = 10 sind also zum Beispiel

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

die teilerfremden Reste.

Weitere Werte der φ-Funktion bis einschließlich 100 können der folgenden Tabelle entnommen werden. So ist zum Beispiel φ(36) = 12.

	1	2	3	4	5	6	7	8	9	10
0 +	1	1	2	2	4	2	6	4	6	4
10 +	10	4	12	6	8	8	16	6	18	8
20 +	12	10	22	8	20	12	18	12	28	8
30 +	30	16	20	16	24	12	36	18	24	16
40 +	40	12	42	20	24	22	46	16	42	20
50 +	32	24	52	18	40	24	36	28	58	16
60 +	60	30	36	32	48	20	66	32	44	24
70 +	70	24	72	36	40	36	60	24	78	32
80 +	54	40	82	24	64	42	56	40	88	24
90 +	72	44	60	46	72	32	96	42	60	40

In graphischer Darstellung zeigen sich interessante Strukturen:

Verlauf der φ-Funktion bis m = 100

Verlauf der φ-Funktion bis m = 500

Verlauf der φ-Funktion bis m = 5000

Nach diesem visuellen Eindruck über das Werteverhalten untersuchen wir nun die allgemeinen Eigenschaften der φ-Funktion. Zunächst gilt (Übung):

Satz (elementare Eigenschaften der φ-Funktion)

Für alle m, n ≥ 1 gilt:

(a)

φ(m) ≥ 1,

(b)	φ(m) = 1 genau dann, wenn m = 1 oder m = 2,

(c)	φ(m) = m − 1 genau dann, wenn m prim.