Unterlagen zur elementaren

Zahlentheorie

Erhard Aichinger

Linz, im Oktober 2005 Alle Rechte vorbehalten Univ.-Doz. Dr. Erhard Aichinger Institut für Algebra Universität Linz 4040 Linz, Österreich

erhard@algebra.uni-linz.ac.at

KAPITEL 1 Rechnen in den ganzen Zahlen

1. Teilbarkeit

Definition 1.1 (Primzahl). Eine Zahl p ∈ ℕ ist genau dann eine Primzahl, wenn folgende beiden Bedingungen gelten:

(1) Es gilt p > 1.
(2) Für alle a, b ∈ ℕ mit p = a · b gilt a = 1 oder b = 1.

Definition 1.2 (Teilbarkeit). Für x, y ∈ ℤ gilt

x teilt y

genau dann, wenn es ein z ∈ ℤ gibt, sodass y = z · x ist.

Wir schreiben dann auch x|y; die Zahl y heißt ein Vielfaches von x;

Satz 1.3. Seien a ∈ ℤ und n ∈ ℕ. Dann gibt es genau ein Paar von Zahlen (q, r), sodass a = q · n + r und r ∈ {0, …, n − 1}.

Wir bezeichnen den Rest r mit a mod b.

Definition 1.4 (Größter gemeinsamer Teiler). Für zwei Zahlen a, b ∈ ℤ (nicht beide 0) ist ggT (a, b) die größte Zahl z ∈ ℕ mit z | a und z | b.

Satz 1.5. Seien a, b ∈ ℤ, nicht beide 0 und sei z ∈ ℤ. Dann gilt:

ggT (a, b) = ggT (a + z · b, b) .

So gilt zum Beispiel ggT (25, 15) = ggT (40, 15).

Beweis: Wir zeigen, dass nicht nur der ggT , sondern sogar die Mengen der gemeinsamen Teiler der beiden Zahlenpaare gleich sind. Wir zeigen also

{t ||| t | a und t | b} = {t ||| t | a + zb und t | b} .

“⊆”: Falls t sowohl a als auch b teilt, dann auch a + zb und b. “⊇”: Falls t sowohl a + zb, als auch b teilt, dann auch a + zb − zb und b, also auch a und b. □

Das nützen wir jetzt möglichst geschickt aus, um ggT (147, 33) zu berechnen:

ggT (147, 33) = ggT (147 − 4 · 33, 33)
= ggT (15, 33)
= ggT (15, 33 − 2 · 15)
= ggT (15, 3)
= ggT (0, 3)
= 3.

Günstig ist es also, z so zu wählen, dass a + zb der Rest von a bei der Division durch b wird.

Mit Hilfe des erweiterten Euklidischen Algorithmus findet man nicht nur den ggT von a und b, sondern auch u, v ∈ Z, sodass gilt:

ggT (a, b) = u · a + v · b.

Beispiel: Wir berechnen ggT (147, 33), und schreiben das so:

147 33
147 1 0 (147 = 1 · 147 + 0 · 33)
33 0 1 (33 = 0 · 147 + 1 · 33)
15 1 -4 (15 = 1 · 146 − 4 · 33)
3 -2 9 (3 = −2 · 147 + 9 · 33)

0

Berechnet man ggT (a, b) mithilfe dieses Algorithmus, sieht man, dass sich die auftretenden Zahlen immer als Linearkombination von a und b schreiben lassen. Als Konsequenz davon erhalten wir folgenden Satz:

Satz 1.6. Seien a, b ∈ ℤ (nicht beide 0). Dann gibt es u, v ∈ ℤ, sodass

ggT (a, b) = u · a + v · b.

Eine Folgerung davon ist:

Satz 1.7. Seien a, b ∈ ℤ, nicht beide 0, und sei t ∈ ℤ so, dass t|a und t|b. Dann gilt auch t|ggT (a, b).

Beweis: Seien u, v ∈ ℤ so, dass ggT (a, b) = ua+vb. Da t die Zahl a teilt, ist auch ua ein Vielfaches von t. Ebenso ist vb ein Vielfaches von t. Somit ist auch die Summe ua + vb ein Vielfaches von t. Die Zahl t ist also ein Teiler von ggT (a, b).

Wenn a und b größten gemeinsamen Teiler 1 haben, so heißen sie teilerfremd oder relativ prim.

Satz 1.8. Seien a, b, c ∈ ℤ, und sei zumindest eine der Zahlen a und b nicht 0. Wir nehmen an, dass a die Zahl b · c teilt, und dass ggT (a, b) = 1 gilt. Dann gilt: a teilt c.

Beweis: Es gibt u, v ∈ ℤ, sodass

1 = u · a + v · b.

Weil a | uac, und da wegen a|bc auch a | vbc gilt, gilt auch

a | (ua + vb)c;

also auch a | c. □

Daraus kann man folgenden Satz herleiten:

Satz 1.9.

(1) Jede natürliche Zahl a ≥ 2 besitzt eine Zerlegung in Primfaktoren

a = p_{1} · . . . · p_{n}.

(2) Die Primfaktorenzerlegung einer natürlichen Zahl a ≥ 2 ist bis auf die Reihenfolge der Primfaktoren eindeutig. Wenn also

a = p_{1} · . . . · p_{n} = q_{1} · . . . · q_{m}

und alle p_{i}, q_{i} Primzahlen sind, dann gilt m = n, und es gibt eine bijektive Abbildung π : {1, …, n} → {1, …, m} , sodass p_{i} = q_{π(i)}.

Sind a, b ∈ ℤ, so nennt man jede Zahl c ∈ ℤ, die von a und b geteilt wird, ein gemeinsames Vielfaches von a und b. Unter allen gemeinsamen Vielfachen zeichnen wir das kleinste aus.

Definition 1.10. Es seien a, b ∈ ℤ \ {0}. Dann ist kgV (a, b) definiert durch

kgV (a, b) = min {v ∈ ℕ ||| a | v und b | v} .

Die Menge aller positiven gemeinsamen Vielfachen ist ja für a, b ∈ ℤ \ {0} bestimmt nicht leer, da sie |a · b| enthält.

Satz 1.11. Seien a, b ∈ ℤ\ {0}, und sei s ∈ ℤ so, dass a | s und b | s. Dann gilt:

kgV (a, b) | s.

Jedes gemeinsame Vielfache ist also ein Vielfaches des kgV .

Beweis: Wir dividieren s durch kgV (a, b) und erhalten somit r ∈ {0, …, kgV (a, b) − 1} und q ∈ ℤ, sodass

s = q · kgV (a, b) + r.

Also gilt r = s − q · kgV (a, b). Sowohl s also auch q · kgV (a, b) sind Vielfache von a und Vielfache von b. Ihre Differenz r ist also ebenfalls ein Vielfaches von a und von b. Da r < kgV (a, b), und da kgV (a, b) das kleinste gemeinsame Vielfache ist, muss r = 0 gelten. Also ist s ein Vielfaches von kgV (a, b).

Zwischen ggT und kgV kann man folgenden Zusammenhang herstellen:

Satz 1.12. Seien a, b ∈ ℕ. Dann gilt

ggT (a, b) · kgV (a, b) = a · b.

Beweis: Wir verwenden die Primfaktorzerlegung von a = ∏ p_{i}^{ν_{i}}, und b = ∏ p_{i}^{σ_{i}}. Aus der Eindeutigkeit der Primfaktorzerlegung kann man herleiten, dass dann gelten muss:

ggT (a, b) = ∏ p_{i}^{min(ν_{i},σ_{i})}
kgV (a, b) = ∏ p_{i}^{max(ν_{i},σ_{i})}.

Daraus folgt:

ggT (a, b) · kgV (a, b) = ∏ p_{i}^{(min(ν_{i},σ_{i})+max(ν_{i},σ_{i}))}
= ∏ p_{i}^{(ν_{i}+σ_{i})}
= a · b.
□

Satz 1.13. Seien a, b, c ∈ ℕ. Dann gilt:

(1) ggT (ggT (a, b), c) = ggT (a, ggT (b, c)).
(2) kgV (kgV (a, b), c) = kgV (a, kgV (b, c)).
(3) ggT (kgV (a, b), c) = kgV (ggT (a, c), ggT (b, c)).
(4) kgV (ggT (a, b), c) = ggT (kgV (a, c), kgV (b, c)).

2. Lösen von Kongruenzen

Definition 1.14. Sei n ∈ ℤ. Dann definieren wir eine Relation ≡_{n} auf ℤ durch

a ≡_{n} b :⇔ n | a − b für a, b ∈ ℤ.

Für a ≡_{n} b schreiben wir auch a ≡ b (mod n) und sagen: “a ist kongruent b modulo n.”

Satz 1.15. Seien a, c ∈ ℤ (nicht beide = 0), und sei b ∈ ℤ. Dann sind die folgenden Bedingungen äquivalent:

(1) Die Kongruenz

ax ≡ b (mod c)

ist lösbar, d. h., es gibt y ∈ ℤ sodass c|a · y − b.

(2) ggT (a, c) teilt b.

Beweis: “(1) ⇒ (2)”: Sei x eine Lösung, d.h. c | ax − b. Falls c die Zahl ax − b teilt, dann gilt erst recht

ggT (a, c) | ax − b.

ggT (a, c) teilt a, also gilt ggT (a, c) | b.

“(2) ⇒ (1)”: Aufgrund der Voraussetzungen existiert ein z ∈ ℤ, sodass

ggT (a, c) · z = b.

Aus dem erweiterten Euklidischen Algorithmus bekommen wir u, v ∈ ℤ mit

ggT (a, c) = u · a + v · c.

Es gilt dann

(ua + vc) · z = b,

also

a · uz + c · vz = b,

und somit

a · (uz) ≡ b (mod c) .

Also ist x := uz Lösung von ax ≡ b ( mod c). □

Satz 1.16. Seien a, c ∈ ℤ (nicht beide = 0), und sei b ∈ ℤ. Sei x_{0} eine Lösung von

(2.1)  ax ≡ b (mod c) .

Dann ist die Lösungsmenge von (2.1) gegeben durch:

L = \{x_{0} + k · \frac{c}{ggT (a, c)} ||| k ∈ ℤ\} .

Beweis: “⊇”: Wir setzen zunächst x_{0} + k \frac{c}{ggT (a,c)} ein und erhalten

a (x_{0} + k \frac{c}{ggT (a,c)}) = ax_{0} + ak \frac{c}{ggT (a,c)}
≡_{c} b + ak \frac{c}{ggT (a,c)}
= b + ck \frac{a}{ggT (a,c)}
≡_{c} b.

Daher ist x_{0} + k \frac{c}{ggT (a,c)} wirklich eine Lösung.

“⊆”: Sei x_{1} Lösung von ax ≡ b (mod c) . Zu zeigen ist: \frac{c}{ggT (a,c)} | (x_{1} − x_{0}). Da x_{1} und x_{0} Lösungen sind, gilt ax_{1} ≡ b (mod c) und ax_{0} ≡ b (mod c). Daher gilt

a (x_{1} − x_{0}) ≡ 0 (mod c) ,

oder, äquivalent dazu,

c | a (x_{1} − x_{0}) .

Daher gilt auch

\frac{c}{ggT (a, c)} | \frac{a}{ggT (a, c)} · (x_{1} − x_{0}) .

Da

ggT (\frac{c}{ggT (a, c)}, \frac{a}{ggT (a, c)}) = 1,

gilt

\frac{c}{ggT (a, c)} | (x_{1} − x_{0}) .

□

Bemerkung: Das System ax ≡ b (mod c) ist also äquivalent zu

x ≡ x_{0} (mod \frac{c}{ggT (a, c)}) ,

wobei x_{0} eine spezielle Lösung von ax ≡ b (mod c) ist.

Wir betrachten nun Systeme von zwei Kongruenzen, also Systeme der Form

\begin{matrix}x ≡ a_{1} (mod m_{1}) \\ x ≡ a_{2} (mod m_{2}) , \end{matrix}

wobei m_{1}, m_{2} ∈ ℕ und a_{1}, a_{2} ∈ ℤ.

Beispiele: Das System

\begin{matrix}x ≡ 1 (mod 2) \\ x ≡ 0 (mod 4) \end{matrix}

kann nicht lösbar sein, denn eine Lösung x ∈ ℤ müsste sowohl gerade als auch ungerade sein. Das System

\begin{matrix}x ≡ 1 (mod 2) \\ x ≡ 2 (mod 5) \end{matrix}

hat zum Beispiel die Lösung x = 7.

Satz 1.17. Seien a_{1}, a_{2} ∈ ℤ, m_{1}, m_{2} ∈ ℕ. Das System

x ≡ a_{1} (mod m_{1})
x ≡ a_{2} (mod m_{2})

ist genau dann lösbar, wenn gilt

ggT (m_{1}, m_{2}) | a_{1} − a_{2}.

Beweis: “⇒”: Wir nehmen an, dass x Lösung ist. Dann gilt: m_{1} | (x − a_{1}) und m_{2} | (x − a_{2}) . Daher gilt auch ggT (m_{1}, m_{2}) | (x − a_{1}) und ggT (m_{1}, m_{2})|(x−a_{2}), und somit

ggT (m_{1}, m_{2}) | (x − a_{2}) − (x − a_{1}) = (a_{1} − a_{2}) .

“⇐” Es gibt u, v ∈ ℤ, sodass

u · m_{1} + v · m_{2} = ggT (m_{1}, m_{2})
k · u · m_{1} + k · v · m_{2} = a_{1} − a_{2}
a_{2} + k · v · m_{2} = \underbrace{a_{1} − k · u · m_{1}}_{=x}

daher ist x := a_{1} − kum_{1} Lösung des Systems. □

Der Beweis liefert auch gleich ein Lösungsverfahren.

Beispiel: Wir lösen:

\begin{matrix}x ≡ 2 (mod 15) \\ x ≡ 8 (mod 21) \end{matrix}

Da ggT (15, 21) = 3 und 3 | (2 − 8) ist das System lösbar. Wir berechnen jetzt diesen ggT und Kofaktoren (d.h. Koeffizienten für eine Linearkombination von 15 und 21, die den ggT ergibt).

21 15 21 1 0 15 0 1 6 1 -1 3 -2 3

und erhalten daraus 3 = 3 · 15 − 2 · 21.

\begin{aligned}3 · 15 − 2 · 21 & = & 3 \\ (−6) · 15 + 4 · 21 & = & 2 − 8 \\ \underbrace{8 + 4 · 21}_{=92} & = & \underbrace{2 + 6 · 15}_{=92} \end{aligned}

Daher erhalten wir eine Lösung: x = 92.

Der folgende Satz gibt an, wie wir aus einer Lösung der Kongruenz alle Lösungen erhalten.

Satz 1.18. Sei x_{0} eine Lösung von

\begin{matrix}x ≡ a_{1} (mod m_{1}) \\ x ≡ a_{2} (mod m_{2}) . \end{matrix}

Dann gilt für die Lösungmenge L

L = {x_{0} + k · kgV (m_{1}, m_{2}) ||| k ∈ ℤ} .

Beweis: “⊇”: Wir setzen

x_{0} + k · kgV (m_{1}, m_{2})

in die erste Kongruenz ein und erhalten

(x_{0} + k · kgV (m_{1}, m_{2})) ≡ a_{1} (mod m_{1}) .

Das gleiche gilt für die zweite Kongruenz.

“⊆”: Wir fixieren x_{1} ∈ L. Um zu zeigen, dass x_{1} ∈ {x_{0} + k · kgV (m_{1}, m_{2}) ||| k ∈ ℤ} , zeigen wir, dass x_{1} − x_{0} ein Vielfaches von kgV (m_{1}, m_{2}) ist. Wir wissen ja, dass

\begin{matrix}x ≡ a_{1} (mod m_{1}) \\ x ≡ a_{2} (mod m_{2}) \end{matrix}

Daher gilt (x_{1} − x_{0}) ≡ 0 (mod m_{1}) und somit m_{1} | (x_{1} − x_{0}). Ebenso zeigt man, dass m_{2} | (x_{1} − x_{0}) gilt.

Da das kgV jedes gemeinsame Vielfache teilt, gilt kgV (m_{1}, m_{2}) | (x_{1} − x_{0}). □

Die folgenden Sätze zeigen uns, wie man das Lösen von Systemen aus mehr als zwei Kongruenzen auf das Lösen von Systemen aus zwei Kongruenzen zurückführen kann. Der erste Satz zeigt, dass man ein System von Kongruenzen durch eine einzige Kongruenz ersetzen kann – vorausgesetzt, man kennt zumindest eine Lösung des Systems.

Satz 1.19. Seien r ∈ ℕ, m_{1}, m_{2}, …, m_{r} ∈ ℕ und a_{1}, a_{2}, …, a_{r} ∈ ℤ. Falls das System

(2.2)

x ≡ a_{1} (mod m_{1})
x ≡ a_{2} (mod m_{2})
⋮
x ≡ a_{r} (mod m_{r})

eine Lösung x_{0} hat, dann ist (2.2) äquivalent zu

x ≡ x_{0} (mod kgV (m_{1}, m_{2}, …, m_{r})) .

Beweisskizze: Falls x_{0} eine Lösung ist, dann ist auch jedes

x_{0} + k · kgV (m_{1}, m_{2}, …, m_{r})

eine Lösung. Andererseits haben zwei verschiedene Lösungen die gleichen Reste modulo jedem m_{i}, ihre Differenz ist daher ein gemeinsames Vielfaches der m_{i} und somit ein Vielfaches des kgV . □

Der folgende Satz sagt, wann ein System von Kongruenzen lösbar ist.

Satz 1.20 (Chinesischer Restsatz). Seien r ∈ ℕ, a_{1}, …, a_{r} ∈ ℤ, m_{1}, …, m_{r} ∈ ℤ \ {0}. Dann sind folgende drei Aussagen äquivalent.

(1) Es gibt x ∈ ℤ, sodass

x ≡ a_{1} (mod m_{1}) x ≡ a_{2} (mod m_{2})

⋮

x ≡ a_{r} (mod m_{r}) .

(2) Für alle i, j ∈ {1, 2, …, r} ist das System

\begin{matrix}x ≡ a_{i} (mod m_{i}) \\ x ≡ a_{j} (mod m_{j}) \end{matrix}

lösbar.

(3) Für alle i, j ∈ {1, 2, …, r} gilt

ggT (m_{i}, m_{j}) | a_{i} − a_{j}.

Beispiel: Wir lösen folgendes System

(2.3)

x ≡ 2 (mod 15)
x ≡ 8 (mod 21)
x ≡ 7 (mod 55)

Wir kennen bereits die Lösungen von x ≡ 2 (mod 15), x ≡ 8 (mod 21). Das System (2.3) ist daher äquivalent zu

\begin{matrix}x ≡ 92 (mod 105) \\ x ≡ 7 (mod 55) . \end{matrix}

Wir berechnen ggT (55, 105) und die Kofaktoren nach dem Euklidschen Algorithmus und erhalten

105 55 105 1 0 55 0 1 50 1 -1 5 -1 2 0

und daher

(−1) · 105 + 2 · 55 = 5
(−17) · 105 + 34 · 55 = 92 − 7
7 + 34 · 55 = 92 + 17 · 105.

Daraus erhalten wir also, dass 1877 die Lösung ist, also geben wir die Lösungsmenge folgendermaßen an:

\begin{aligned}L & = & \{x ∈ ℤ ||| x ≡ 1877 (mod 1155)\} \\ & = & \{x ∈ ℤ ||| x ≡ 722 (mod 1155)\}. \end{aligned}

3. Der Ring ℤ_{n}

In ℤ definieren wir für n ∈ ℕ die Relation ≡_{n} durch

a ≡_{n} b :⇔ n | b − a.

Alle zu a kongruenten Elemente fassen wir zu einer Restklasse modulo n zusammen. Wir nennen diese Kallse [a]_{n}.

[a]_{n} := {a + z · n ||| z ∈ ℤ}

Die Menge aller Restklassen modulo n bezeichnen wir mit ℤ_{n}.

ℤ_{n} = {[a]_{n} ||| a ∈ ℤ} .

ℤ_{n} hat n Elemente, und zwar [0]_{n} , [1]_{n} , …, [n − 1]_{n} . Auf ℤ_{n} definieren wir ⊕ und ⊙ durch:

[a]_{n} ⊕ [b]_{n} := [a + b]_{n}
[a]_{n} ⊙ [b]_{n} := [a · b]_{n} .

Wir müssen zeigen, dass ⊕ und ⊙ wohldefiniert sind; wir geben hier nur den Beweis für die Wohldefiniertheit von ⊙. Wir wählen also a, a′, b, b′ ∈ ℤ sodass [a]_{n} = [a′]_{n} und [b]_{n} = [b′]_{n}. Zu zeigen ist, dass dann

[a · b]_{n} = [a′ · b′]_{n}

gilt. Es ist also zu zeigen:

n | a · b − a′ · b′
n | a · b − ab′ + ab′ − a′b′
n | a · (b − b′) + b′ · (a − a′) .

Das gilt, denn laut Vorraussetzung gilt n | (b − b′) und n | (a − a′). Daher ist [a · b]_{n} = [a′ · b′]_{n}, und somit ist das Ergebnis von [a]_{n} ⊙ [b]_{n} unabhängig von der Auswahl der Repräsentanten.

Wir geben nun ein Beispiel für eine nicht wohldefinierte Operation. Auf der Menge ℚ definieren wir die Relation

a ∼ b :⇔ ⌊a⌋ = ⌊b⌋ .

Wir definieren:

⌊a⌋ ⊙ ⌊b⌋ := ⌊a · b⌋ .

\begin{matrix}a = 0.1 & b = 100 & ⌊0.1 · 100⌋ = 10 \\ a′ = 0 & b′ = 100 & ⌊0 · 100⌋ = 0 \end{matrix}

Da 0 ≁ 10, ist die Operation ⊙ ist also nicht wohldefiniert.

3. DER RING ℤ_{n} 13

Mengen mit Operationen bezeichnet man als algebraische Strukturen. Strukturen, in denen man drei Operationen zur Verfügung hat, die bestimmte, von den Grundrechnungsarten in ganzen Zahlen bekannte, Rechengesetze erfüllen, heißen Ringe. Wir betrachten im folgenden Ringe mit Eins; ein Ring mit Eins hat zwei zweistellige Operationen (+, ·), eine einstellige Operation (−) und zwei nullstellige Operationen (0, 1).

Definition 1.21. (R, +, −, ·, 0, 1) heißt Ring mit Eins genau dann, wenn für alle x, y, z ∈ R die folgenden Eigenschaften erfüllt sind:

(1) x + 0 = x

(2) x + (−x) = 0

(3) (x + y) + z = x + (y + z)

(4) x + y = y + x

(5) (x · y) · z = x · (y · z)

(6) (x + y) · z = x · z + y · z

(7) x · (y + z) = x · y + x · z

(8) 1 · x = x

(9) x · 1 = x.

So ist zum Beispiel (ℤ, +, −, ·, 0, 1) ein Ring mit Eins.

Satz 1.22. Sei (R, +, −, ·, 0, 1) ein Ring mit Eins. Dann gelten für alle x, y ∈ R folgende Eigenschaften:

(1) 0 · x = 0

(2) x · (−y) = −(x · y)

(3) (−x) · y = −(x · y)

(4) x · 0 = 0.

Definition 1.23. Ein Element a ∈ ℤ_{n} heißt invertierbar, falls es ein b ∈ ℤ_{n} gibt, sodass

a · b = [1]_{n} .

Beispiel: Betrachten wir etwa ℤ_{6} :

[1]_{6} ist invertierbar  [1]_{6} · [1]_{6} = [1]_{6}
[2]_{6} ist nicht invertierbar
[3]_{6} ist nicht invertierbar
[4]_{6} ist nicht invertierbar
[5]_{6} ist invertierbar  [5]_{6} · [5]_{6} = [1]_{6}
[0]_{6} ist nicht invertierbar

Beispiel: In ℤ_{5} gilt:

[1]_{5} · [1]_{5} = [1]_{5}
[2]_{5} · [3]_{5} = [1]_{5}
[3]_{5} · [2]_{5} = [1]_{5}
[4]_{5} · [4]_{5} = [1]_{5}
[0]_{5} ist aber nicht invertierbar.

Der folgende Satz gibt an, welche Elemente in ℤ_{n} invertierbar sind.

Satz 1.24 (Invertierbarkeit). Sei n ∈ ℕ und a ∈ ℤ. Dann ist [a]_{n} genau dann invertierbar in ℤ_{n}, wenn ggT (a, n) = 1.

Satz 1.25. Seien a, b invertierbare Elemente aus ℤ_{n}. Dann ist auch a · b invertierbar.

Beweis: Seien u, v ∈ ℤ_{n} so, dass a·u = [1]_{n} und b·v = [1]_{n} . Dann gilt: a·b·v ·u = [1]_{n}. □

Definition 1.26 (Euler’sche φ−Funktion). Sei n ∈ ℕ, n > 1. Dann ist φ(n) definiert durch

φ (n) := |{a ∈ ℤ_{n} ||| a invertierbar}| =
= |{x ∈ {1, 2, …, n − 1} ||| ggT (x, n) = 1}| .

Wir berechnen φ (12) = |{1, 5, 7, 11}| = 4 und φ (8) = |{1, 3, 5, 7}| = 4.

Satz 1.27 (Satz von Euler). Sei n ∈ ℕ, n > 1, a ∈ ℤ, ggT (a, n) = 1. Dann gilt:

a^{φ(n)} ≡ 1 (mod n) .

Wir überprüfen diesen Satz durch zwei Beispiele:

• Gilt 7^{φ(12)} ≡ 1 (mod 12)? Ja, denn es ist 7^{4} ≡ 1 (mod 12),
• Gilt 3^{φ(5)} ≡ 1 (mod 5)? Ja, denn es gilt 3^{4} ≡ 1 (mod 5).

Beweis von Satz 1.27: Wir wählen n ∈ ℕ und a ∈ ℤ beliebig aber fest, und nehmen an, dass ggT (a, n) = 1. Sei

I := {x ∈ ℤ_{n} ||| x ist invertierbar} .

Wir wissen bereits, dass |I| = φ (n). Wir definieren

\begin{aligned}f & : & I & ⟶ & ℤ_{n} \\ & & x & ⟼ & x ⊙ [a]_{n} \end{aligned}

und zeigen, dass f injektiv ist. Dazu fixieren wir x, y ∈ I mit f (x) = f (y). Das heißt: x · [a]_{n} = y · [a]_{n}. Da ggT (a, n) = 1, gibt es b ∈ ℤ mit [a]_{n} · [b]_{n} = [1]_{n} . Wir erhalten also x · [a]_{n} · [b]_{n} = y · [a]_{n} · [b]_{n} und damit x = y. Daher ist f injektiv. Nun zeigen wir:

f (I) = I.

“⊆”: Wir fixieren x ∈ f (I). Es gibt also y ∈ I, sodass x = y · [a]_{n}. Da y ∈ I, ist y invertierbar, und somit ist auch y · [a]_{n} = x invertierbar.

“⊇”: Sei x ∈ I. Wir wählen b ∈ ℤ mit [b]_{n} · [a]_{n} = [1]_{n}. Das Element x · [b]_{n} ist invertierbar und es gilt f(x · [b]_{n}) = x. Also ist x wirklich das Bild eines invertierbaren Elements und liegt somit in f(I).

Die Funktion f ist also eine bijektive Abbildung von I nach I.

Es gilt also:

∏_{x∈I} x = ∏_{x∈I} f (x)
∏_{x∈I} x = ∏_{x∈I} (x · [a]_{n})

∏_{x∈I} x = (∏_{x∈I} x) · ([a]_{n})^{φ(n)}

Sei y ∈ ℤ_{n} das Inverse zu ∏_{x∈I} x. Dann gilt:

y · ∏_{x∈I} x = y · (∏_{x∈I} x) . ([a]_{n})^{φ(n)}

[1]_{n} = ([a]_{n})^{φ(n)}
1 ≡ a^{φ(n)} (mod n) .
□

Korollar 1.28. Sei p eine Primzahl, und sei z ∈ ℤ. Dann gilt

z^{p} ≡ z (mod p) .

Falls p kein Teiler von z ist, gilt

z^{p−1} ≡ 1 (mod p) .

Beweis: Wir wählen eine Primzahl p und z ∈ ℤ beliebig, aber fest, und nehmen an, dass p die Zahl z nicht teilt. Wir wissen, dass φ (p) = p − 1, und daher gilt nach dem Satz von Euler

z^{p−1} ≡ 1 (mod p) .

Da p|(z^{p−1} − 1), gilt auch p|(z^{p} − z), und somit z^{p} ≡ z (mod p).

Wenn p | z, dann teilt p sowohl z als auch z^{p}. □

Satz 1.29. Für alle a, b ∈ ℤ_{p} gilt: (a + b)^{p} = a^{p} + b^{p}.

Satz 1.30. Seien p, q Primzahlen, p ≠ q und seien a, s ∈ ℤ. Dann gilt:

a^{1+s(p−1)(q−1)} ≡ a (mod p · q) .

Beweis:

• 1. Fall: ggT (a, pq) = 1: Wir wissen ja, dass a^{p−1} ≡ 1 (mod p) gilt (Satz von Euler), daher gilt auch (a^{p−1})^{(q−1)·s} ≡ 1 (mod p). Somit ist p ein Teiler von a^{(p−1)·(q−1)·s} − 1 und damit auch von a^{(p−1)·(q−1)·s+1} − a. Ebenso zeigen wir

q | a^{(p−1)·(q−1)·s+1} − a.

Damit gilt insgesamt:

pq | a^{(p−1)·(q−1)·s+1} − a.

• 2. Fall: ggT (a, pq) = p: Da der ggT (a, q) = 1 ist, gilt mit dem Satz von Euler a^{q−1} ≡ 1 (mod q) , und somit a^{(q−1)·(p−1)} ≡ 1 (mod q). Das heißt

q | a^{(q−1)·(p−1)·s} − 1.

Wir wissen ja, dass p | a. Daher gilt p · q | (a^{(q−1)·(p−1)·s} − 1) · a.

• 3. Fall: ggT (a, pq) = q: Beweis genauso wie im 2. Fall.

• 4. Fall: ggT (a, pq) = p·q: Dann ist zu zeigen, dass 0 ≡ 0 ( mod pq). □

Satz 1.31 (Multiplikativität der φ-Funktion). Seien n, m ∈ ℕ, n ≥ 2, m ≥ 2. Wenn n, m relativ prim sind, dann gilt

φ (n · m) = φ (n) · φ (m) .

Der Beweis der Multiplikativität erfordert noch etwas Information über Ringe.

Satz 1.32. Falls R_{1} und R_{2} Ringe mit Eins sind, dann ist

(R_{1} × R_{2}, +_{R_{1}×R_{2}}, −_{R_{1} ×R_{2}}, ·_{R_{1}×R_{2}}, 0_{R_{1}×R_{2}}, 1_{R_{1}×R_{2}})

wieder ein Ring mit Eins. Dabei sind die Verknüpfungen auf R_{1} × R_{2} definiert durch

• ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} ) +_{R_{1}×R_{2}} ( \begin{matrix}s_{1} \\ s_{2} \end{matrix} ) := ( \begin{matrix}r_{1} +_{R_{1}} s_{1} \\ r_{2} +_{R_{2}} s_{2} \end{matrix} )

• ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} ) ·_{R_{1}×R_{2}} ( \begin{matrix}s_{1} \\ s_{2} \end{matrix} ) := ( \begin{matrix}r_{1} ·_{R_{1}} s_{1} \\ r_{2} ·_{R_{2}} s_{2} \end{matrix} )

• −_{R_{1}×R_{2}} ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} ) := ( \begin{matrix}−_{R_{1}} r_{1} \\ −_{R_{2}} r_{2} \end{matrix} )

• 0_{R_{1}×R_{2}} := ( \begin{matrix}0_{R_{1}} \\ 0_{R_{2}} \end{matrix} )

• 1_{R_{1}×R_{2}} := ( \begin{matrix}1_{R_{1}} \\ 1_{R_{2}} \end{matrix} ).

R_{1} × R_{2} mit diesen Operationen erfüllt auch alle Ring mit Eins-Rechengesetze.

Rechnen wir zum Beispiel in ℤ_{4} × ℤ_{5}.

( \begin{matrix}[3] & 4 \\ [4] & 5 \end{matrix} ) · ( \begin{matrix}[2] & 4 \\ [3] & 5 \end{matrix} ) = ( \begin{matrix}[2] & 4 \\ [2] & 5 \end{matrix} )

R_{1} × R_{2} heißt das direkte Produkt von R_{1} und R_{2}.

Definition 1.33. R, S seien Ringe mit Eins. Die Abbildung φ : R → S heißt Ring mit Eins-Homomorphismus: ⇔

∀r_{1}, r_{2} ∈ R : φ (r_{1} +_{R} r_{2}) = φ (r_{1}) +_{S} (r_{2}) ,
φ (−_{R} r_{1}) = −_{S} φ (r_{1}) ,
φ (r_{1} ·_{R} r_{2}) = φ (r_{1}) ·_{S} φ (r_{2}) ,
φ (0_{R}) = 0_{S},
φ (1_{R}) = 1_{S}.

Definition 1.34. Ein Homomorphismus φ heißt:

• Epimorphismus :⇔ φ ist surjektiv;

• Monomorphismus :⇔ φ ist injektiv;

• Isomorphismus :⇔ φ ist bijektiv.

Beispiel: Wollen wir uns dies zunächst an zwei Beispielen veranschaulichen.

• φ : ℤ → ℤ_{5}, z ↦ [x]_{5} ist surjektiv, aber nicht injektiv. Also ist φ ein Epimorphismus.

• Wir untersuchen α : ℤ_{5} → ℤ, [x]_{5} ↦ x. Hier ergibt sich folgendes Problem: α ([3]_{5}) = 3, und α ([3]_{5}) = α ([8]_{5}) = 8. — Das Problem ist, dass α nicht wohldefiniert ist. Man kann das auch so ausdrücken, dass man sagt, dass die Relation

α = {([x]_{5} , x) ||| x ∈ ℤ}

nicht funktional (d. h. eine Funktion = Graph einer Funktion) ist. Sie ist nicht funktional, weil ([2]_{5} , 2) ∈ α und ([2]_{5} , 7) ∈ α.

Definition 1.35. Sei R ein Ring mit Eins. Dann heißt r ∈ R invertierbar, falls es ein y_{r} ∈ R gibt, sodass

r · y_{r} = 1_{R} und y_{r} · r = 1_{R}.

Satz 1.36. Seien n, m ∈ ℕ mit ggT (n, m) = 1. Dann ist die Abbildung

\begin{aligned}φ & : & ℤ_{m·n} & ⟶ & ℤ_{n} × ℤ_{m} \\ & & [x]_{m·n} & ⟼ & ([x]_{n} , [x]_{m}) \end{aligned}

ein Ring mit Eins-Isomorphismus.

Beweis: Wir führen den Beweis in drei Schritten.

(1) φ ist wohldefiniert: Zu zeigen ist, dass für alle y, z ∈ ℤ mit [y]_{m·n} = [z]_{m·n} die Gleichheiten [y]_{n} = [z]_{n} und [y]_{m} = [z]_{m} gelten. Zu zeigen ist ist also, dass für alle y, z ∈ ℤ gilt:

m · n | y − z ⇒ (m | y − z ∧ n | y − z) .

Das ist aber offensichtlich.

(2) φ ist Homomorphismus: Wir überprüfen die Homomorphismuseigenschaft für +. Wir berechnen dazu

φ ([x]_{n·m} + [y]_{n·m}) = φ ([x + y]_{n·m})

= ([x + y]_{n} , [x + y]_{m}) = ([x]_{n} + [y]_{n} , [x]_{m} + [y]_{m})

= ( \begin{matrix}[x] & n \\ [x] & m \end{matrix} ) + ( \begin{matrix}[y] & n \\ [y] & m \end{matrix} )

= φ ([x]_{n·m}) + φ ([y]_{n·m}) .

(3) φ ist bijektiv: Da beide Mengen endlich und gleich groß sind, reicht es, zu zeigen, dass φ injektiv ist. Wir nehmen also an φ ([x]_{nm}) = φ ([y]_{nm}). Das heißt ([x]_{n} , [x]_{m}) = ([y]_{n} , [y]_{m}). Daher gilt n | x−y und m | x−y. Da der ggT (n, m) = 1 ist, gilt: n · m | x − y. Wir erhalten daher [x]_{nm} = [y]_{nm}. Die Abbildung φ ist also injektiv, somit surjektiv und damit bijektiv. □

Wenn der ggT (n, m) = 1 ist, dann ist ℤ_{n}×ℤ_{m} also isomorph zu ℤ_{n·m}. Da Isomorphismen die Invertierbarkeit erhalten, haben beide Ringe gleich viele invertierbare Elemente. Daraus können wir jetzt die Multiplikativität der φ−Funktion, also Satz 1.31, herleiten.

Beweis von Satz 1.31:

(1) Anzahl der invertierbaren Elemente von ℤ_{n} ×ℤ_{m}: Wir zeigen, dass \binom{a}{b} ∈ ℤ_{n} × ℤ_{m} genau dann invertierbar ist, wenn a invertierbar in ℤ_{n} und b invertierbar in ℤ_{m} ist. Dazu fixieren wir zunächst \binom{a}{b} ∈ ℤ_{n} × ℤ_{m} und nehmen an, dass \binom{a}{b} invertierbar ist; es gibt also \binom{c}{d} ∈ ℤ_{n} × ℤ_{m}, sodass \binom{a}{b} · \binom{c}{d} = 1_{ℤ_{n}×ℤ_{m}} = (\begin{matrix}[1] & _{n} \\ [1] & _{m} \end{matrix}). Daher ist a in ℤ_{n} invertierbar (mit Inversem c), ebenso b in ℤ_{m} (mit Inversem d).

Nun fixieren wir a ∈ ℤ_{n}, b ∈ ℤ_{m}, beide invertierbar. Falls a · c = [1]_{n} , und b · d = [1]_{m} , dann ist \binom{c}{d} das Inverse zu \binom{a}{b}. In ℤ_{n} gibt es φ (n) invertierbare Elemente, in ℤ_{m} gibt es φ (m) invertierbare Elemente, und somit gibt es in ℤ_{n} × ℤ_{m} genau φ (n) · φ (m) invertierbare Elemente.

(2) Anzahl der invertierbaren Elemente in ℤ_{n·m}: Hier gibt es φ (n · m) invertierbare Elemente (nach der Definition von φ).

Damit ist

φ (n · m) = φ (n) · φ (m)

für n, m ∈ ℕ mit ggT (n, m) = 1 bewiesen. □

Aus der Primfaktorzerlegung von n und aus φ(p^{α}) = p^{α} − p^{α−1} kann man jetzt leicht φ(n) durch

φ (n) = φ (∏ p_{i}^{α_{i}})
= ∏ φ (p_{i}^{α_{i}})
= ∏ p_{i}^{α_{i}} (1 − \frac{1}{p_{i}} )
= ∏ p_{i}^{α_{i}} · ∏ (1 − \frac{1}{p_{i}} )
= n · ∏ (1 − \frac{1}{p_{i}} )

berechnen. Dazu noch ein Beispiel:

Beispiel: φ (12) = 12 · (1 − \frac{1}{2}) · (1 − \frac{1}{3}) = 4 = 2 · 2 = φ (3) · φ (4).