ParAlg, Kapitel 7.2

7.2 Modulare Arithmetik und Primzahlen

Wir wollen hier das Argument mit der Matrix vollen Ranges aus dem vorherigen Kapitel in seiner Gesamtheit ausführen. Zur Erinnerung: wir haben zwei verschiedene Elemente $s_{1}, s_{2} \in Z_{p}$ und zwei (nicht notwenigerweise verschiedene) Zahlen $z_{1}, z_{2}$ und wollen zeigen, dass das Gleichungssystem

\begin{aligned} a s_{1} + b & \equiv_{p} z_{1} \\ a s_{2} + b & \equiv_{p} z_{2} . \end{aligned}

genau eine Lösung hat. In einem ersten Schritt bilden wir die Differenz der Gleichungen:

\begin{array}{r} a (s_{1} - s_{2}) \equiv_{p} z_{1} - z_{2} . \end{array}

Dies ist eine Gleichung in einer Unbekannten: $a$ . Der Einfachheit halber schreiben wir nun $s := s_{1} - s_{2}$ und $z := z_{1} - z_{2}$ und erhalten

\begin{array}{r} a s \equiv_{p} z, \end{array}

eine Gleichung in einer Unbekannten. Wir werden nun zeigen, dass $a s \equiv_{p} z$ genau eine Lösung hat. Sobald wir dies wissen, sehen wir per $b \equiv_{p} z_{1} - a s_{1}$ , dass es auch für $b \in Z_{p}$ eine eindeutige Lösung gibt, und somit hat das Gleichungssystem genau eine Lösung und es folgt $Pr [(π (s_{1}), π (s_{2})) = (z_{1}, z_{2})] = 1 / p^{2}$ . Wir müssen also nur zeigen, dass $a s \equiv_{p} z$ genau eine Lösung in $Z_{p}$ hat. Dabei gilt $s ≢_{p} 0$ , da $s_{1}, s_{2} \in Z_{p}$ verschieden sind und somit $s_{1} - s_{2}$ nicht $0$ und auch sonst nicht durch $p$ teilbar sein kann.

Wären $s$ und $z$ rationale Zahlen und hätten wir statt $\equiv_{p}$ eine Gleichheit $=$ , dann würden wir $a s = z$ einfach zu $a = z / s$ auflösen. Es ist aber nicht klar, dass wir in $Z_{p}$ auch dividieren können (wir können es; ich will aber den ganzen Weg zu Fuß gehen).

Lemma 7.2.1 Sei $p$ eine Primzahl, $s \in Z_{p}$ nicht $0$ und $z \in Z_{p}$ . Dann gibt es genau ein $a \in Z_{p}$ mit $a s \equiv_{p} z$ .

Beweis. Wir probieren es einfach mal aus. Wir nehmen $p = 13$ , $s = 4$ und $z = 5$ . Wir legen eine Tabelle an, in der wir für jedes $a \in Z_{p}$ den Wert $4 a \mod p$ schreiben:

Ja, die 5 kommt genau einmal vor, und somit hat die Gleichung $4 a \equiv_{p} 5$ genau eine Lösung, nämlich $11$ . Strenggenommen hat sie natürlich unendlich viele: $11 + 13 l$ für jedes $l \in Z$ . Daher sagten wir: genau eine in $Z_{p}$ . Wir sehen aber noch mehr: jede Zahl in $Z_{p}$ kommt genau einmal vor. Wir behaupten: Sei $0 \neq s \in Z_{p}$ . Dann ist die Funktion $f : a \mapsto a s \mod p$ bijektiv. Da $f : Z_{p} \to Z_{p}$ ist, Definitions- und Wertebereich also gleich groß, gilt noch mehr: wenn $f$ injektiv ist, dann ist die automatisch bijektiv. Es reicht somit, wenn wir zeigen, dass $f$ injektiv ist.

Nehmen wir an, $f$ wäre nicht bijektiv. Dann gäbe es $0 \leq a_{1} < a_{2} \leq p - 1$ mit

\begin{array}{r} a_{1} s \equiv_{p} a_{2} s, \end{array}

also (a_1 - a_2) s \equiv_p 0. Setze $t := a_{1} - a_{2}$ . Da $a_{1}$ und $a_{2}$ ungleich und beide kleiner als $p$ sind, ist $t = a_{1} - a_{2}$ nicht durch $p$ teilbar. Genauso wenig wie $s$ . Dagegen ist $s t = (a_{1} - a_{2}) s \equiv_{p}$ und somit ist $s t$ durch $p$ teilbar. Fassen wir zusammen:

\begin{aligned} p ∤ & s \\ p ∤ & t \\ p | & t . \end{aligned}

Dies kann nicht geschehen, da $p$ eine Primzahl ist. $◻$

Der letzte ist vielleicht nicht ganz offensichtlich. Beweisen wir ihn.

Lemma 7.2.2 (Lemma von Euklid). Sei $p \in Z$ eine Primzahl und seien $s, t \in Z$ . Wenn $p | s t$ , dann gilt auch $p | s$ oder $p | t$ .

Daraus folgt per Induktion die allgemeinere Aussage: wenn $p | s_{1} s_{2} \dots s_{k}$ , dann gilt $p | s_{i}$ für mindestens ein $1 \leq i \leq k$ .

Fehlerhafter Beweis. Lemma 7.2.2 klingt für Sie vielleicht offensichtlich. Das folgt doch aus der Primfaktorzerlegung! Probieren wir es. Wir zerlegen

s

und

t

in ihre Primfaktoren:

\begin{aligned} s & = p_{1} p_{2} \dots p_{k} \\ t & = q_{1} q_{2} \dots q_{l} . \end{aligned}

s t

durch

p

teilbar ist, schreiben wir

s t = p r

und zerlegen

r

in seine Primfaktoren:

\begin{aligned} r & = r_{1} r_{2} \dots r_{m} . \end{aligned}

Wir haben nun zwei Primfaktorzerlegungen von $s t$ , nämlich

\begin{aligned} (1) & s t & = p r_{1} r_{2} \dots r_{m} \\ (2) & s t & = p_{1} p_{2} \dots p_{k} \cdot q_{1} q_{2} \dots q_{l} . \end{aligned}

Wegen der Eindeutigkeit der Primfaktorzerlegung müssen ( $1$ ) und ( $2$ ) bis auf Anordnung gleich sein. Da ( $1$ ) die Primzahl $p$ enthält, so muss auch ( $2$ ) es enthalten, also muss $p$ eines der $p_{i}$ oder eines der $q_{j}$ sein, und somit gilt $p | s$ oder $p | t$ .

Für diesen Beweis haben wir die Eindeutigkeit der Primfaktorzerlegung benötigt. Beweisen wir die doch mal.

Lemma 7.2.3 Eine natürliche Zahl $s$ lässt sich eindeutig (bis auf Umordnung) als Produkt

\begin{array}{r} s = p_{1} p_{2} \dots p_{k} \end{array}

von Primzahlen schreiben.

Beweis. Nehmen wir zum Zwecke des Widerspruchs an, dem sei nicht so, und es gäbe tatsächlich zwei verschiedene Primfaktorzerlegungen von $s$ .

\begin{aligned} s & = p_{1} p_{2} \dots p_{k} \\ t & = q_{1} q_{2} \dots q_{l} \end{aligned}

Insbesondere erhalten wir die Gleichung

\begin{array}{r} p_{1} p_{2} \dots p_{k} = q_{1} q_{2} \dots q_{l} \end{array}

Ohne Beschränkung der Allgemeinheit können wir annehmen, dass kein $p_{i}$ auf der rechten Seite vorkommt, da wir sonst beide Seiten durch $p_{i}$ dividieren könnten. Es gilt nun also, dass $p_{1}$ die linke Seite teilt und somit auch die rechte Seite. Allerdings teilt $p_{1}$ keines der Faktoren. Dies ist ein Widerspruch zu Lemma 7.2.2

◻

Nun haben wir uns aber im Kreis gedreht. Lemma 7.2.2 haben wir mit Hinweis auf die Eindeutigkeit der Primfaktorzerlegung bewiesen; letztere wiederum mithilfe von Lemma 7.2.2. So geht das nicht. Nein, wir müssen Lemma 7.2.2 beweisen, ohne die Eindeutigkeit der Primfaktorzerlegung bereits anzunehmen.

Für einen anständigen Beweis brauchen wir folgendes Lemma:

Lemma 7.2.4 (Lemma von Bézout). Seien $a, b \in Z$ , nicht beide $0$ . Dann gibt es Zahlen $s, t \in Z$ mit $ggT (a, b) = s \cdot a + t \cdot b$ . Mit $ggT (a, b)$ bezeichnen wir den größten gemeinsamen Teiler von $a$ und $b$ .

Beweis. Da $ggT (a, b) = ggT (| a |, | b |)$ gilt, können wir annehmen, dass $a, b \geq 0$ . Wir verwenden Induktion über $a + b$ . Wenn $min (a, b) = 0$ gilt, sagen wir $b = 0$ , dann ist $ggT (a, 0) = a$ und $1 \cdot a + 0 \cdot 0 = a$ . Die gesuchten Zahlen $s, t$ sind also zum Beispiel $1$ und $0$ . Wenn $a, b \geq 1$ gilt, dann sei ohne Beschränkung der Allgemeinheit $a \geq b$ . Da $ggT (a, b) = ggT (b, a - b)$ gilt und $b + (a - b) < a + b$ , schließen wir per Induktion, dass es Zahlen $s^{'}, t^{'}$ gibt mit $s^{'} b + t^{'} (a - b) = ggT (a, b)$ . Somit ist

\begin{array}{r} ggT (a, b) = s^{'} b + t^{'} (a - b) = s^{'} b + t^{'} a - t^{'} b = t^{'} a + (s^{'} - t^{'}) b \end{array}

und wir können $s := t^{'}$ und $t := s^{'} - t^{'}$ setzen.

Am Besten sieht man es an einem konkreten Beispiel:

\begin{array}{r} \begin{aligned} 100 - 61 & = 39 & 39 = 100 - 61 \\ 61 - 39 & = 22 & 22 = 61 - 39 = 61 - (100 - 61) = 2 \cdot 61 - 100 \\ 39 - 22 & = 17 & 17 = 39 - 22 = (100 - 61) - (2 \cdot 61 - 100) = 2 \cdot 100 - 3 \cdot 61 \\ 22 - 17 & = 5 & 5 = 22 - 17 = (2 \cdot 61 - 100) - (2 \cdot 100 - 3 \cdot 61) = 5 \cdot 61 - 3 \cdot 100 \\ 17 - 5 & = 12 & 12 = 17 - 5 = (2 \cdot 100 - 3 \cdot 61) - (5 \cdot 61 - 3 \cdot 100) = 5 \cdot 100 - 8 \cdot 61 \\ 12 - 5 & = 7 & 7 = 12 - 5 = (5 \cdot 100 - 8 \cdot 61) - (5 \cdot 61 - 3 \cdot 100) = 8 \cdot 100 - 13 \cdot 61 \\ 7 - 5 & = 2 & 2 = 7 - 5 = (8 \cdot 100 - 13 \cdot 61) - (5 \cdot 61 - 3 \cdot 100) = 11 \cdot 100 - 18 \cdot 61 \\ 5 - 2 & = 3 & 3 = 5 - 2 = (5 \cdot 61 - 3 \cdot 100) - (11 \cdot 100 - 18 \cdot 61) = 23 \cdot 61 - 14 \cdot 100 \\ 3 - 2 & = 1 & 1 = 3 - 2 = (23 \cdot 61 - 14 \cdot 100) - (11 \cdot 100 - 18 \cdot 61) = 41 \cdot 61 - 25 \cdot 100 \end{aligned} \end{array}

$◻$

Beweis von Lemma 7.2.2. Wir zeigen: wenn $p | s t$ und $p ∤ s$ , dann gilt $p | t$ . Dies ist äquivalent zur Aussage des Lemmas. Da $p ∤ s$ gilt, muss $ggT (p, s) = 1$ gelten (Warum? Die Primzahl $p$ hat als Teiler nur $1$ und $p$ , also muss der ggT entweder $1$ oder $p$ sein; $p$ kann er wegen $p ∤ s$ nciht sein). Nach Bézouts Lemma gibt es $a$ und $b$ mit

\begin{array}{r} a p + b s = 1 \end{array}

Wir multiplizieren beide Seiten mit $t$ und erhalten

\begin{array}{r} a p t + b s t = t \end{array}

Nun sehen wir: $p$ teilt $s t$ , also auch $b s t$ . Somit teilt es beide Summanden der linken Seite. Somit teilt $p$ die linke Seite, also auch die rechte, und es gilt: $p | t$ , wie behauptet. $◻$

Wir haben nun Lemma 7.2.2 bewiesen, ohne die Eindeutigkeit der Primfaktorzerlegung zu verwenden. Letztere ist, wie wir ja oben im "fehlerhaften Beweis" gesehen haben, eine Konsequenz aus dem Lemma. Insofern haben wir nun auch bewiesen:

Theorem 7.2.5 (Fundamentalsatz der Arithmetik)