§ 2 Der euklidische Algorithmus in ℤ

(2.12) Der euklidische Algorithmus (EA)

Seien a, b ∈ ℕ . Die Folgen (r_{k})_{k≥0} , (q_{k})_{k≥1} seien rekursiv definiert durch:

r_{0} := a , r_{1} := b. Für k ∈ ℕ_{0} sei q_{k+1} der Quotient und r_{k+2} der Rest bei Division von r_{k} durch r_{k+1} , falls r_{k+1} ≠ 0 , d.h.

(⋆) r_{k} = q_{k+1} · r_{k+1} + r_{k+2} mit 0 ≤ r_{k+2} < r_{k+1}

Dann gibt es eine Zahl n ∈ ℕ mit r_{n} ≠ 0 und r_{n+1} = 0 , wobei gilt

r_{n} = ggT(a, b)

\underline{Bew:} Wir führen wiederholte Division mit Rest aus. Dies ist solange möglich, wie die Zahl, durch die geteilt ist, von 0 verschieden ist.

r_{0} = a , r_{1} = b
r_{0} = q_{1} · r_{1} + r_{2} mit 0 ≤ r_{2} < r_{1}
r_{1} = q_{2} · r_{2} + r_{3} mit 0 ≤ r_{3} < r_{2}
r_{2} = q_{3} · r_{3} + r_{4} mit 0 ≤ r_{4} < r_{3}
⋮
r_{k} = q_{k+1} · r_{k+1} + r_{k+2} mit 0 ≤ r_{k+2} < r_{k+1}
⋮

Annahme: r_{k} > 0 ∀ k ≥ 2. Dann folgt b = r_{1} > r_{2} > r_{3} > r_{4} > … > r_{k} > … > 0 , d.h. es gibt unendlich viele natürliche Zahlen < b. Widerspruch! Folglich gibt es ein n ∈ ℕ mit r_{n+1} = 0 und r_{n} ≠ 0 . Zu zeigen bleibt, daß r_{n} wirklich der ggT von a und b ist. Dazu schreiben wir noch einmal das Divisionsschema auf:

r_{0} = a , r_{1} = b

r_{0} = q_{1} · r_{1} + r_{2} mit 0 < r_{2} < r_{1} r_{1} = q_{2} · r_{2} + r_{3} mit 0 < r_{3} < r_{2} r_{2} = q_{3} · r_{3} + r_{4} mit 0 < r_{4} < r_{3}

⋮

r_{n−2} = q_{n−1} · r_{n−1} + r_{n} mit 0 < r_{n} < r_{n−1}

r_{n−1} = q_{n} · r_{n} + \underbrace{r_{n+1}}_{=0}

Aus der letzten Gleichung folgt r_{n} | r_{n−1} , so daß nach (2.9c) gilt: r_{n} = ggT(r_{n}, r_{n−1}) . Mit (2.10) und den obigen Gleichungen ergibt sich

\underline{\underline{ggT(a, b)}} = ggT(r_{0}, r_{1}) = ggT(r_{1}, r_{2}) = ggT(r_{2}, r_{3}) = … = ggT(r_{n−1}, r_{n}) = \underline{\underline{r_{n}}}

•

\underline{\underline{(2.13) BEM:}} Der ggT von a, b ∈ ℤ läßt sich im Falle a ≠ 0 und b ≠ 0 nach (2.9b) berechnen durch ggT(a, b) = ggT(|a|, |b|), da dann |a|, |b| ∈ ℕ gilt. Ansonsten ist ggT(a, 0) = |a| nach (2.9d), insbesondere ist ggT(0, 0) = 0 .

Der erweiterte euklidische Algorithmus (EEA)

Nach (2.8) gibt es zu a, b ∈ ℤ immer Zahlen x, y ∈ ℤ mit ggT(a, b) = xa + yb. Wir wollen nun den EA so erweitern, daß wir neben ggT(a, b) auch diese Koeffizienten x und y berechnen können. Die Bezeichnungen seien wie in (2.12) gewählt: r_{0} := a , r_{1} := b

r_{0} = q_{1}r_{1} + r_{2}  0 < r_{2} < r_{1}
r_{1} = q_{2}r_{2} + r_{3}  0 < r_{3} < r_{2}
⋮
r_{k} = q_{k+1}r_{k+1} + r_{k+2} 0 < r_{k+2} < r_{k+1} (0 ≤ k < n − 2)
⋮
r_{n−2} = q_{n−1}r_{n−1} + r_{n}  0 < r_{n} < r_{n−1}
r_{n−1} = q_{n}r_{n}  (r_{n+1} = 0)
r_{n} = ggT(a, b)

Wir schreiben jetzt diese Gleichungen in Matrizen–Form um:

(1)  ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} ) =  ( \begin{matrix}q_{1}r_{1} + r_{2} \\ r_{1} \end{matrix} ) = ( \begin{matrix}r_{0} \\ r_{1} \end{matrix} ) = ( \begin{matrix}a \\ b \end{matrix} )
(2)  ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}r_{2} \\ r_{3} \end{matrix} ) =  ( \begin{matrix}q_{2}r_{2} + r_{3} \\ r_{2} \end{matrix} ) = ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} )
⋮
(k)  ( \begin{matrix}q_{k} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}r_{k} \\ r_{k+1} \end{matrix} ) = ( \begin{matrix}q_{k}r_{k} + r_{k+1} \\ r_{k} \end{matrix} ) = ( \begin{matrix}r_{k−1} \\ r_{k} \end{matrix} )
⋮
(n − 1) ( \begin{matrix}q_{n−1} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}r_{n−1} \\ r_{n} \end{matrix} ) = ( \begin{matrix}q_{n−1}r_{n−1} + r_{n} \\ r_{n−1} \end{matrix} ) = ( \begin{matrix}r_{n−2} \\ r_{n−1} \end{matrix} )
(n)  ( \begin{matrix}q_{n} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}r_{n} \\ r_{n+1} \end{matrix} ) = ( \begin{matrix}q_{n}r_{n} + r_{n+1} \\ r_{n} \end{matrix} ) = ( \begin{matrix}r_{n−1} \\ r_{n} \end{matrix} )

Chr. Nelius : Mathematik am Computer , WS 2006/07 3 Sukzessives Einsetzen ergibt:

( \begin{matrix}a \\ b \end{matrix} ) =^{(1)} ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}r_{1} \\ r_{2} \end{matrix} ) =^{(2)} ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}r_{2} \\ r_{3} \end{matrix} ) =^{(3)} …

=^{(n−1)} ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) · . . . · ( \begin{matrix}q_{n−1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}r_{n−1} \\ r_{n} \end{matrix} )

=^{(n)} ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) · . . . · ( \begin{matrix}q_{n} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}r_{n} \\ r_{n+1} \end{matrix} )

= \underbrace{( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) · . . . · ( \begin{matrix}q_{n} & 1 \\ 1 & 0 \end{matrix} )}_{=:A} ( \begin{matrix}g \\ 0 \end{matrix} )

Die Matrix A hat ganzzahlige Elemente und ist als Produkt invertierbarer Matrizen selbst wieder invertierbar:

det ( \begin{matrix}x & 1 \\ 1 & 0 \end{matrix} ) = −1 (∀ x ∈ ℤ) ⟹ det(A) = (−1)^{n}.

A · ( \begin{matrix}g \\ 0 \end{matrix} ) = ( \begin{matrix}a \\ b \end{matrix} ) ⟹ ( \begin{matrix}g \\ 0 \end{matrix} ) = A^{−1} · ( \begin{matrix}a \\ b \end{matrix} )

Das Inverse von A berechnen wir über die adjungierte Matrix: es ist A^{−1} = det(A)^{−1} · A^{ad}. Ist A = ( \begin{matrix}α & β \\ γ & δ \end{matrix} ) ∈ M_{2}(ℤ) , so ist A^{ad} = ( \begin{matrix}δ & −β \\ −γ & α \end{matrix} ) ∈ M_{2}(ℤ) . Folglich

A^{−1} = det(A)^{−1}·( \begin{matrix}δ & −β \\ −γ & α \end{matrix} ) = (−1)^{n} ( \begin{matrix}δ & −β \\ −γ & α \end{matrix} ) = ( \begin{matrix}(−1)^{n}δ & (−1)^{n+1}β \\ (−1)^{n+1}γ & (−1)^{n}α \end{matrix} ) ∈ M_{2}(ℤ)

und A^{−1} · ( \begin{matrix}a \\ b \end{matrix} ) = ( \begin{matrix}(−1)^{n}δa + (−1)^{n+1}βb \\ ⋆ \end{matrix} ) = ( \begin{matrix}g \\ 0 \end{matrix} )

Also: g = \underbrace{((−1)^{n}δ)}_{=:x} ·a + \underbrace{((−1)^{n+1}β)}_{=:y} ·b mit x := (−1)^{n}A[2, 2] , y := (−1)^{n+1}A[1, 2] ∈ ℤ.

Zusammenfassend erhalten wir:

(2.14) Der erweiterte euklidische Algorithmus (EEA)

Mit der Bezeichnungsweise von (2.12) gilt:

Die (2 × 2)–Matrix A := ( \begin{matrix}q_{1} & 1 \\ 1 & 0 \end{matrix} ) · ( \begin{matrix}q_{2} & 1 \\ 1 & 0 \end{matrix} ) · . . . · ( \begin{matrix}q_{n} & 1 \\ 1 & 0 \end{matrix} ) ist invertierbar, und es ist A^{−1} · ( \begin{matrix}a \\ b \end{matrix} ) = ( \begin{matrix}g \\ 0 \end{matrix} ) mit g = ggT(a, b). Insbesondere ist

g = ((−1)^{n}A[2, 2]) · a + (−1)^{n+1}A[1, 2]) · b

\underline{\underline{(2.15) BEM:}} a) In einer Darstellung ggT(a, b) = xa + yb (x, y ∈ ℤ) sind die Koeffizienten nicht eindeutig bestimmt, es gibt sogar unendlich viele Möglichkeiten: ggT(2, 3) = 1 = (−1) · 2 + 1 · 3 = 2 · 2 + (−1) · 3 = 5 · 2 + (−3) · 3 = (−4) · 2 + 3 · 3.

b) Sei g = ggT(a, b) und gelte g = x_{0}a + y_{0}b mit x_{0}, y_{0} ∈ ℤ. Dann folgt

g = (x_{0} + t · \frac{b}{g} ) a + (y_{0} − t · \frac{a}{g}) b (∀ t ∈ ℤ)

und dies sind alle möglichen Darstellungen von g.

c) Der EEA berechnet den ggT g von a, b ∈ ℕ und Zahlen x, y ∈ ℤ mit g = xa + yb. Seien jetzt a, b ∈ ℤ \ {0}. Nach (2.9b) gilt dann

g = ggT(a, b) = ggT(|a|, |b|) .

Mit dem EEA (2.14) lassen sich x′, y′ ∈ ℤ berechnen mit

g = x′ · |a| + y′ · |b| .

Um nun g als Linearkombination von a und b darzustellen, benutzen wir die Vorzeichenfunktion, die für x ∈ ℝ definiert ist durch

sign (x) := \{ \begin{matrix}1 & für x > 0 \\ 0 & für x = 0 \\ −1 & für x < 0 \end{matrix}

Insbesondere gilt |x| = sign (x) · x. Es folgt

g = (\underbrace{x′ · sign (a)}_{=x∈ℤ}) · a + (\underbrace{y′ · sign (b)}_{=y∈ℤ}) · b

Für b = 0 ist |a| = ggT(a, 0) = sign (a) · a + 1 · b. •

\underline{\underline{(2.16) DEF:}} a_{1}, a_{2}, …, a_{n} (n ≥ 2) seien ganze Zahlen. Eine ganze Zahl g heißt ggT von a_{1}, a_{2}, …, a_{n} (in Zeichen: g = ggT(a_{1}, a_{2}, …, a_{n})) , wenn gilt:

i) g ≥ 0 ii) g|a_{i} für alle i = 1, 2, …, n iii) Für ein beliebiges t ∈ ZZ mit t|a_{i} für alle i = 1, 2, …, n folgt t|g,.

\underline{\underline{(2.17) SATZ:}} Für a, b, c ∈ ZZ gilt ggT(a, b, c) = ggT(ggT(a, b), c) .

\underline{\underline{(2.18) BEM:}} Für ganze Zahlen a_{1}, a_{2}, …, a_{n} (n ≥ 3) gilt:

a) ggT(a_{1}, a_{2}, …, a_{n}) = ggT(ggT(a_{1}, a_{2}, …, a_{n−1}), a_{n})

b) ggT(a_{1}, a_{2}, …, a_{n}) existiert und ist eindeutig bestimmt.