Chr.Nelius , Mathematik für Informatiker I (WS 2000/01) 22.12.2000

\underline{\underline{(9.6) SATZ:}} Division mit Rest

Zu a ∈ ZZ und n ∈ IN existieren eindeutig bestimmte ganze Zahlen q und r mit

a = qn + r und 0 ≤ r < n

Hierbei heißt q der Quotient bei Division von a durch n und r der Rest bei Division von a durch n.

\underline{Bew:} Idee: Subtrahiere von a > 0 solange n, bis eine Zahl zwischen 0 und n − 1 übrigbleibt.

Setze q := ⌊\frac{a}{n}⌋ und r := a − qn .

Dann gilt: q, r ∈ ZZ und a = qn + r . Noch z.z.: 0 ≤ r < n .

Für alle x ∈ IR gilt: ⌊x⌋ ≤ x < ⌊x⌋ + 1 , woraus 0 ≤ x − ⌊x⌋ < 1 folgt. Für x = \frac{a}{n} ergibt

sich dann: 0 ≤ \frac{a}{n} − ⌊\frac{a}{n}⌋ = \frac{a}{n} − q < 1 | · n ⟹ 0 ≤ \underbrace{a − qn}_{=r} < n

\underline{Bezeichnungen:} Gelte a = qn + r mit 0 ≤ r < n . Dann setzen wir q =: a div n und r =: a mod n.

\underline{\underline{(9.7) FOLG:}} Für a ∈ ZZ und n ∈ IN gilt: n|a ⟺ a mod n = 0

Eine rationale Zahl r ist ein Bruch zweier ganzer Zahlen

r = \frac{a}{b} (a, b ∈ ZZ, b ≠ 0)

Für jede rationale Zahl gibt es unendlich viele solcher Darstellungen der Form

r = \frac{ak}{bk} (k ∈ ZZ \ \{0\})

Um zu einer möglichst einfachen Darstellung zu kommen, kürzt man gemeinsame Faktoren von Zähler und Nenner heraus, z.B.

\frac{36}{42} = \frac{2̸ · 18}{2̸ · 21} = \frac{3̸ · 6}{3̸ · 7} = \frac{6}{7}

Die Zahlen 6 und 7 haben jetzt keinen gemeinsamen Teiler ≠ ±1, sie sind teilerfremd. Mit einem Schlage erhält man diese Darstellung, indem man den größten gemeinsamen Teiler von Zähler und Nenner herauskürzt. Man kommt dann zu der eindeutigen Darstellung einer rationalen Zahl

r = \frac{c}{d} mit c ∈ ZZ, d ∈ IN, c und d teilerfremd

Die folgende Definition für den ggT ist so formuliert, daß sie leicht auf andere Bereiche (z.B. für Polynome) übertragen werden kann.

\underline{\underline{(9.8) DEF:}} Seien a und b ganze Zahlen. Eine Zahl g ∈ ZZ heißt größter gemeinsamer Teiler (ggT) von a und b, wenn folgendes gilt:

i) g ≥ 0

ii) g | a und g | b
iii) ∀ t ∈ ZZ : t | a und t | b ⟹ t | g

Bezeichnung: g = ggT(a, b)

\underline{\underline{(9.9) BEM:}} a) i) liefert die Eindeutigkeit des ggT’s (s.b)) , ii) bedeutet, daß g ein gemeinsamer Teiler von a und b ist und iii) besagt, daß g von jedem gemeinsamen Teiler von a und b geteilt wird.

b) Zu a, b ∈ ZZ gibt es höchstens einen ggT.

\underline{Bew:} Seien g und g′ ggT’s von a und b. Dann folgt aus (9.8), daß g und g′ sich gegenseitig teilen, woraus nach (9.3c) |g| = |g′| folgt. Wegen i) ergibt sich hieraus g = g′.

c) Im Falle g = ggT(a, b) ≠ 0 ist g auch wirklich der größte unter den gemeinsamen Teilern von a und b .

\underline{Bew:} Ist t ∈ ZZ ein beliebiger gemeinsamer Teiler von a und b, so folgt aus iii) t | g , woraus sich mit (9.3b) ergibt t ≤ |t| ≤ |g| = g.

d) ggT(a, b) = ggT(|a|, |b|)

e) ggT(a, b) = ggT(b, a)

f) ggT(a, b) = |a| ⟺ a | b.

Im folgenden zeigen wir, daß zu je zwei ganzen Zahlen stets der ggT existiert. Dies geschieht dadurch, daß wir ein Verfahren zur Berechnung des ggT’s angeben (euklidischer Algorithmus). Das folgende Lemma ist Grundlage für eine Berechnungsmethode des ggT’s:

\underline{\underline{(9.10) LEMMA:}} Seien a, b, q, r ∈ ZZ mit a = qb + r . Dann gilt ggT(a, b) = ggT(b, r).

Im Falle b > 0 gilt insbesondere ggT(a, b) = ggT(b, a mod b)

\underline{Bew:} Die Aussage ist so zu verstehen, daß ggT(b, r) existiert und gleich ggT(a, b) ist, wenn ggT(a, b) existiert und umgekehrt.

Gezeigt wird, daß die Zahlenpaare (a, b) und (b, r) dieselben gemeinsamen Teiler haben.

Für ein beliebiges t ∈ ZZ mit t | a und t | b folgt mit (9.3f) auch t | (a−qb) , d.h. t | r. Umgekehrt folgt aus t | b und t | r auch t | (qb + r) , also t | a.

Existiere nun g := ggT(a, b) . Dann gilt i) g ≥ 0 . ii) Nach obiger Überlegung ist g auch ein gemeinsamer Teiler von b und r . iii) Sei t ∈ ZZ ein beliebiger gemeinsamer Teiler von b und r. Dann ist t auch ein gemeinsamer Teiler von a und b, also t | g , da g := ggT(a, b) . Damit ist g auch ggT von b und r. Die Umkehrung geht analog.

\underline{\underline{Beispiel:}} Wir wollen den ggT von a = 48 und b = 18 berechnen.

Division mit Rest ergibt 48 = 2 · 18 + 12 , also ggT(48, 18) = ggT(18, 12) nach (9.10) Division mit Rest ergibt 18 = 1 · 12 + 6 , also ggT(18, 12) = ggT(12, 6) nach (9.10). Nun gilt nach (1.9f) ggT(12, 6) = 6 , da 6 | 12. Insgesamt erhalten wir: ggT(48, 18) = ggT(18, 12) = ggT(12, 6) = 6 , womit wir den ggT berechnet haben. Wir werden sehen, daß dieses Verfahren immer den ggT zweier ganzer Zahlen liefert (euklidischer Algorithmus). Indem wir die Divisionsgleichungen jeweils nach dem Rest auflösen und in die vorhergehende Gleichung einsetzen, erhalten wir

\begin{aligned}6 & = & 18 − 1 · 12 \\ & = & 18 − (48 − 2 · 18) = 3 · 18 − 48 \end{aligned}

Damit haben wir den ggT von 48 und 18 als ganzzahlige Linearkombination von 48 und 18 dargestellt:

6 = ggT(48, 18) = (−1) · 48 + 3 · 18

Auch diese Möglichkeit der Darstellung des ggT’s ist immer gegeben, wie wir gleich sehen werden.

(9.11) Der erweiterte euklidische Algorithmus

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

r_{0} := a , r_{1} := b. Für k ∈ IN_{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}

x_{0} := 1 , x_{1} := 0 (⋆⋆) x_{k+1} := x_{k−1} − q_{k} · x_{k} ∀ k ≥ 1

y_{0} := 0 , y_{1} := 1 (⋆⋆⋆) y_{k+1} := y_{k−1} − q_{k} · y_{k} ∀ k ≥ 1

Dann gilt :

a) ∀ k ≥ 0 : r_{k} = x_{k} · a + y_{k} · b

b) Es gibt eine Zahl m ∈ IN mit r_{m} ≠ 0 und r_{m+1} = 0 , und es ist

r_{m} = ggT(a, b) = x_{m} · a + y_{m} · b

\underline{\underline{BEM:}} Zur Berechnung des ggT’s mit Hilfe des einfachen euklidischen Algorithmus (EA) benötigt man nur die beiden Hilfsfolgen (r_{k})_{k≥0} und (q_{k})_{k≥1} . Der erweiterte euklidische Algorithmus (EEA) liefert zusätzlich die Darstellung des ggT’s von a und b als ganzzahlige Linearkombination der beiden Zahlen a und b .

\underline{Bew:} a) Wir führen Induktion nach k ∈ IN_{0} : (IA) \underline{k = 0} x_{0} · a + y_{0} · b = 1 · a + 0 · b = a = r_{0}

\underline{k = 1} x_{1} · a + y_{1} · b = 0 · a + 1 · b = b = r_{1} (IV) Sei k ∈ IN beliebig und gelte die Behauptung für k − 1 und k, d.h.

r_{k−1} = x_{k−1}a + y_{k−1}b und r_{k} = x_{k}a + y_{k}b (IB) r_{k+1} = x_{k+1}a + y_{k+1}b Nach (⋆) für k−1 gilt r_{k+1} = r_{k−1}−q_{k}r_{k}. Setzt man für r_{k−1} und r_{k} die IV ein, so erhält man:

r_{k+1} = (x_{k−1}a + y_{k−1}b) − q_{k}(x_{k}a + y_{k}b)
= \underbrace{(x_{k−1} − q_{k}x_{k})}_{=x_{k+1} (⋆⋆)} a + \underbrace{(y_{k−1} − q_{k}y_{k})}_{=y_{k+1} (⋆⋆⋆)} b
= x_{k+1}a + y_{k+1}b

b) 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 m ∈ IN mit r_{m+1} = 0 und r_{m} ≠ 0 . Zu zeigen bleibt, daß r_{m} 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_{k} = q_{k+1} · r_{k+1} + r_{k+2} mit 0 < r_{k+2} < r_{k+1}

⋮

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

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

Aus der letzten Gleichung folgt r_{m} | r_{m−1} , so daß nach (9.9f) gilt: r_{m} = ggT(r_{m}, r_{m−1}) . Mit (9.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_{m−1}, r_{m}) = \underline{\underline{r_{m}}} Die Darstellung des ggT’s ergibt sich unmittelbar aus a). Danach gilt

\underline{\underline{ggT(a, b)}} = r_{m} = \underline{\underline{x_{m} · a + y_{m} · b}} mit x_{m}, y_{m} ∈ ZZ

\underline{\underline{Beispiel:}} Seien a := 3473 , b := 1311 . Es sollen der ggT und die Darstellung des ggT’s bestimmt werden.

(EA)  k r_{k−2} = q_{k−1}r_{k−1} + r_{k}
0  r_{0} = a  r_{0} = 3473
1  r_{1} = b  r_{1} = 1311
2  r_{0} = q_{1} · r_{1} + r_{2}  3473 = 2 · 1311 + 851
3  r_{1} = q_{2} · r_{2} + r_{3}  1311 = 1 · 851 + 460
4  r_{2} = q_{3} · r_{3} + r_{4}  851 = 1 · 460 + 391
5  r_{3} = q_{4} · r_{4} + r_{5}  460 = 1 · 391 + 69
6  r_{4} = q_{5} · r_{5} + r_{6}  391 = 5 · 69 + 46
7  r_{5} = q_{6} · r_{6} + r_{7}  69 = 1 · 46 + 23
8  r_{6} = q_{7} · r_{7} + r_{8}  46 = 2 · 23 + 0

Es ist also r_{8} = 0 . Folglich 23 = r_{7} = ggT(3473, 1311)

(EEA)  k 0  1  2 3 4 5 6  7 8
r_{k} 3473 1311 851 460 391 69 46 23 0
q_{k} −  2  1 1 1 5 1  2 −
x_{k} 1  0  1 −1 2 −3 17 −20 −
y_{k} 0  1 −2 3 −5 8 −45 53 −

23 = ggT(3473, 1311) = (−20) · 3473 + 53 · 1311

Aus (9.11) erhält man nun das folgende Ergebnis:

\underline{\underline{(9.12) SATZ:}} Zu je zwei ganzen Zahlen a und b existiert der eindeutig bestimmte ggT. Außerdem gibt es Zahlen x, y ∈ ZZ mit ggT(a, b) = x · a + y · b . (Diese Zahlen x und y sind nicht eindeutig bestimmt).

\underline{Bew:} \underline{1. Fall: a, b ∈ IN} Die Behauptung ergibt sich aus (9.11) und (9.9b) \underline{2. Fall: a = 0, b ∈ ZZ bel.} Hier gilt ggT(a, b) = |b| = 0 · a + sign (b) · b \underline{3. Fall: a ∈ ZZ bel. , b = 0} Hier gilt ggT(a, b) = |a| = sign (a) · a + 0 · b \underline{4. Fall: a, b ∈ ZZ bel.} Nach (9.9d) gilt ggT(a, b) = ggT(|a|, |b|) , und ggT(|a|, |b|) existiert nach den vorherigen Fällen, da |a|, |b| ∈ IN_{0} . Außerdem gibt es x′, y′ ∈ ZZ mit

\underline{\underline{ggT(a, b)}} = ggT(|a|, |b|) = x′ · |a| + y′ · |b| = \underbrace{(x′ · sign (a))}_{=:x} ·a + \underbrace{(y′ · sign (b))}_{=:y} ·b
= \underline{\underline{x · a + y · b}} mit x, y ∈ ZZ