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{align*} as_1 + b & \equiv_p z_1 \\ as_2 + b & \equiv_p z_2 \ . \end{align*}genau eine Lösung hat. In einem ersten Schritt bilden wir die Differenz der Gleichungen:
\begin{align*} a (s_1 - s_2) \equiv_p z_1 - z_2 \ . \end{align*}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{align*} a s \equiv_p z \ , \end{align*}eine Gleichung in einer Unbekannten. Wir werden nun zeigen, dass $as \equiv_p z$ genau eine Lösung hat. Sobald wir dies wissen, sehen wir per $b \equiv_p z_1 - as_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[ (\pi(s_1),\pi(s_2)) = (z_1, z_2)] = 1/p^2$. Wir müssen also nur zeigen, dass $as \equiv_p z$ genau eine Lösung in $\Z_p$ hat. Dabei gilt $s \not \equiv_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 $as = 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).
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 $as \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 $4a \mod p$ schreiben:
Ja, die 5 kommt genau einmal vor, und somit hat die Gleichung $4a \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 \ne s \in \Z_p$. Dann ist die Funktion $f: a \mapsto as \mod p$ bijektiv. Da $f : \Z_p \rightarrow \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 \lt a_2 \leq p-1$ mit
\begin{align*} a_1 s \equiv_p a_2 s \ , \end{align*}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 $st = (a_1 - a_2)s \equiv_p$ und somit ist $st$ durch $p$ teilbar. Fassen wir zusammen:
\begin{align*} p \nmid & s \\ p \nmid & t \\ p | & t \ . \end{align*}Dies kann nicht geschehen, da $p$ eine Primzahl ist. \(\square\)
Der letzte ist vielleicht nicht ganz offensichtlich. Beweisen wir ihn.
(Lemma von Euklid). Sei $p \in \Z$ eine Primzahl und seien $s,t \in \Z$. Wenn $p | st$, dann gilt auch $p | s$ oder $p|t$.
Daraus folgt per Induktion die allgemeinere Aussage: wenn $p | s_1 s_2 \cdots s_k$, dann gilt $p | s_i$ für mindestens ein $1\leq i \leq k$.
Wir haben nun zwei Primfaktorzerlegungen von $st$, nämlich
\begin{align} st & = p r_1 r_2 \cdots r_m \label{decomp-1}\\ st & = p_1 p_2 \cdots p_k \cdot q_1 q_2 \cdots q_l \ . \label{decomp-2} \end{align}Wegen der Eindeutigkeit der Primfaktorzerlegung müssen (\ref{decomp-1}) und (\ref{decomp-2}) bis auf Anordnung gleich sein. Da (\ref{decomp-1}) die Primzahl $p$ enthält, so muss auch (\ref{decomp-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.
Eine natürliche Zahl $s$ lässt sich eindeutig (bis auf Umordnung) als Produkt
\begin{align*} s = p_1 p_2 \cdots p_k \end{align*}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{align*} s & = p_1 p_2 \cdots p_k\\ t & = q_1 q_2 \cdots q_l\\ \end{align*}Insbesondere erhalten wir die Gleichung
\begin{align*} p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l \end{align*}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
\(\square\)Nun haben wir uns aber im Kreis gedreht. haben wir mit Hinweis auf die Eindeutigkeit der Primfaktorzerlegung bewiesen; letztere wiederum mithilfe von . So geht das nicht. Nein, wir müssen beweisen, ohne die Eindeutigkeit der Primfaktorzerlegung bereits anzunehmen.
Für einen anständigen Beweis brauchen wir folgendes Lemma:
(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) \lt 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{align*} \ggt(a,b) = s'b + t'(a-b) = s'b + t'a - t'b = t'a + (s' - t') b \end{align*}und wir können $s := t'$ und $t := s'-t'$ setzen.
Am Besten sieht man es an einem konkreten Beispiel:
\begin{align*} \begin{array}{rl|l} 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{array} \end{align*}\(\square\)
Beweis von . Wir zeigen: wenn $p | st$ und $p \nmid s$, dann gilt $p | t$. Dies ist äquivalent zur Aussage des Lemmas. Da $p \nmid 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 \nmid s$ nciht sein). Nach Bézouts Lemma gibt es $a$ und $b$ mit
\begin{align*} ap + bs = 1 \end{align*}Wir multiplizieren beide Seiten mit $t$ und erhalten
\begin{align*} apt + bst = t \end{align*}Nun sehen wir: $p$ teilt $st$, also auch $bst$. 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.\(\square\)
Wir haben nun 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:
(Fundamentalsatz der Arithmetik)