Modulare Arithmetik

Fundamentalsatz der Arithmetik

Das folgende Lemma stammt vom französischen Mathematiker Étienne Bézout (1730-1783). Die Aussage des Lemmas ist außerordentlich wichtig. Wir benötigen sie anschließend für den Beweis des Lemmas von Euklid, welches wir wiederum für den Beweis des Fundamentalsatzes der Arithmetik brauchen. Darüber hinaus werden wir das Lemma später konstruktiv in der Kryptografie anwenden.

Satz: Lemma von Bézout

Seien \(a, b \in \mathbb{Z}\) mit \(a \not = 0\). Dann gibt es Zahlen \(s, t \in \mathbb{Z}\) mit \(ggT(a, b) = sa + tb\).

Beweis:

Die Behauptung ergibt sich aus dem Euklidischen Algorithmus. Hierzu stellen wir die Gleichungen nach den Resten um und erhalten: \[r_1 = b - q_1a\] \[r_2 = a - q_2r_1\] \[r_3 = r_1 - q_3r_2\] \[\vdots\] \[r_n = r_{n-2} - q_nr_{n-1}\]

Durch Anwendung der vollständigen Induktion kann man nun zeigen, dass es Zahlen \(s_i, t_i \in \mathbb{Z}\) gibt mit \(r_i = s_ia + t_ib\) für alle \(1 \leq i \leq n\).

Induktionsanfang: Für \(r_1\) ist die Aussage offenbar richtig, indem man \(s_1 := -q_1\) und \(t_1 := 1\) wählt. Indem man \(r_1\) in die Gleichung \(r_2 = a - q_2r_1\) einsetzt, erhält man \(r_2 = a - q_2(b - q_1a) = a - q_2b + q_1q_2a = (1 + q_1q_2)a - q_2b\). Somit gilt die Aussage auch für \(r_2\) mit \(s_2 := 1 + q_1q_2\) und \(t_2 := -q_2\).

Induktionsschritt: Wir zeigen nun, dass die Aussage auch für alle folgenden Reste richtig ist. Hierzu sei \(1 \lt i \lt n\). Wir betrachten \(r_{i+1} = r_{i-1} - q_{i+1}r_i\). Gemäß dem Induktionsanfang gilt die Aussage für \(r_i\) und \(r_{i-1}\) und es ist \(r_i = s_ia + t_ib\) und \(r_{i-1} = s_{i-1}a + t_{i-1}b\). Wir setzen \(r_i\) und \(r_{i-1}\) in die Gleichung von \(r_{i+1}\) ein und erhalten \(r_{i+1} = (s_{i-1}a + t_{i-1}b) - q_{i+1}(s_ia + t_ib) = s_{i-1}a + t_{i-1}b - q_{i+1}s_ia - q_{i+1}t_ib = (s_{i-1} - q_{i+1}s_i)a + (t_{i-1} - q_{i+1}t_i)b\). Somit gilt die Aussage für \(r_{i+1}\) mit \(s_{i+1} := s_{i-1} - q_{i+1}s_i\) und \(t_{i+1} := t_{i-1} - q_{i+1}t_i\).

Die Gültigkeit der Behauptung folgt dann mit \(s := s_n\) und \(t := t_n\). \(\square\)

Der Beweis zum Lemma von Bézout liefert uns somit die konstruktive Antwort darauf, wie wir die Zahlen \(s\) und \(t\) berechnen können: Wir stellen die Gleichungen nach den Resten um und setzen dann wie im Beweis sukzessive ein. Das Ergebnis ist \(s\) und \(t\). Man nennt diese Zahlen auch Bézout-Koeffizienten. Die Berechnung dieser Zahlen wird für den RSA-Algorithmus eine wichtige Rolle spielen. Wir wollen das Vorgehen noch einmal an einigen Beispielen verdeutlichen.

Beispiel: Lemma von Bézout

1. Seien wie im Beispiel zum Euklidischen Algorithmus \(a := 1071\) und \(b := 1029\). Wir haben oben gesehen, dass \(ggT(1071, 1029) = 21\) ist. Nun wollen wir Zahlen \(s\) und \(t\) berechnen, sodass \(21 = s \cdot 1071 + t \cdot 1029\) ist. Wir gehen hierzu wie im vorangegangenen Beweis vor. Folgende Gleichungen haben wir oben bei der Durchführung des Euklidischen Algorithmus gebildet: \[1071 = 1 \cdot 1029 + 42\] \[1029 = 24 \cdot 42 + 21\] \[42 = 2 \cdot 21 + 0\] Wir stellen diese Gleichungen nach den Resten um (die letzte Gleichung müssen wir dabei natürlich nicht betrachten, denn dort ist der Rest 0 und die Umstellung würde lediglich \(0 = 0\) liefern) und erhalten: \[42 = 1071 - 1029\] \[21 = 1029 - 24 \cdot 42\] Wir setzen die erste Gleichung in die zweite ein und erhalten: \[21 = 1029 - 24 \cdot (1071 - 1029)\] \[= 1029 - 24 \cdot 1071 + 24 \cdot 1029\] \[= 25 \cdot 1029 + (-24) \cdot 1071\] Die gesuchten Zahlen sind somit \(s := -24\) und \(t := 25\).