§ 4. ggT und kgV

\underline{(4.1) DEF:} Eine ganze Zahl g heißt größter gemeinsamer Teiler (ggT) zweier ganzer Zahlen a und b, wenn gilt: GGT_{0}) g ≥ 0 GGT_{1}) g | a und g | b GGT_{2}) Für alle t ∈ Z mit t | a und t | b folgt t | g. Bezeichnung: g = ggT(a, b) .

GGT_{0}) hat die Eindeutigkeit des ggT’s zur Folge (s. Bem. (4.2)). GGT_{1}) besagt, daß g ein gemeinsamer Teiler von a und b ist. GGT_{2}) bedeutet, daß g von jedem gemeinsamen Teiler von a und b geteilt wird.

\underline{(4.2) BEM:} Zu je zwei ganzen Zahlen gibt es höchstens einen ggT .

\underline{(4.3) SATZ:} Zu je zwei ganzen Zahlen a und b existiert immer ein eindeutig bestimmter ggT g, und es gibt x, y ∈ ℤ mit der Eigenschaft

g = xa + yb ,

(d.h. g läßt sich als ganzzahlige Linearkombination von a und b darstellen) .

\underline{Bew:} 1) Eindeutigkeit folgt aus (4.2)

2) Existenz Seien a, b ∈ ℤ. Da ℤ ein HIB ist, ist das Summenideal ℤa + ℤb ein Hauptideal, d.h. es gibt (genau ein) g ∈ ℕ_{0} mit der Eigenschaft

ℤa + ℤb = ℤg .

GGT_{1}) und GGT_{2}) folgen dann sofort mit Hilfe von (3.17) . Wegen g ∈ ℤa + ℤb ergibt sich dann die behauptete Darstellung für g. •

(4.4) LEMMA:

Rechenregeln für den ggT

Für alle a, b ∈ ℤ gilt:

a) ggT(a, b) = ggT(b, a)  b) ggT(a, b) = | a | ⟺ a | b
c) ggT(a, 0) = | a |  d) ggT(0, 0) = 0
e) ggT(a, b) = 0 ⟺ (a = b = 0) f) ggT(a, b) = ggT(| a |, | b |)

\underline{(4.5) BEM:} zur Namensgebung “ggT”:

Für a, b ∈ ℤ sei GT^{+}(a, b) := T^{+}(a)∩T^{+}(b) die Menge der nichtnegativen gemeinsamen Teiler. Im Falle a, b ∈ ℕ ist GT^{+}(a, b) endlich und nichtleer und besitzt daher ein bzgl. ≤ größtes Element. Dieses ist gerade

ggT(a, b) = max((GT^{+}(a, b), ≤)) .

Dagegen gilt im Falle a = b = 0

GT^{+}(a, b) = T^{+}(a) ∩ T^{+}(b) = ℕ_{0} ∩ ℕ_{0} = ℕ_{0} ,

d.h. ggT(a, b) = 0 ist nicht mehr die (bzgl. ≤) größte Zahl in der Menge der (nichtnegativen) gemeinsamen Teiler von a und b.

In der geordneten Menge (ℕ_{0}, |) ist jedoch ggT(a, b) für alle a, b ∈ ℕ_{0} das (bzgl. |) größte Element in der Menge der nichtnegativen gemeinsamen Teiler von a und b, d.h.

ggT(a, b) = max((GT^{+}(a, b), |)) .

Das Nullelement spielt also keine Sonderrolle mehr.

Ein effizientes Verfahren zur Berechnung des ggT’s zweier natürlicher Zahlen liefert der allen bekannte euklidische Algorithmus (EA) . Grundlage dafür ist das folgende

\underline{(4.6) LEMMA:} Für a ∈ ℤ und b ∈ ℕ gilt ggT(a, b) = ggT(b, a mod b) .

(4.7) 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 für alle 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 . Die letzten beiden Gleichungen des obigen Schemas lauten damit

\begin{matrix}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} \end{matrix}

Mit Hilfe von (4.6) ergibt sich nun

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

Dabei gilt die letzte Gleichheit wegen r_{n} | r_{n−1} . •

Eine Modifizierung des EA zum erweiterten euklidischen Algorithmus ermöglicht es, auch Koeffizienten für die Darstellung des ggT’s als ganzzahlige Linearkombination zu berechnen:

(4.8) Der erweiterte euklidische Algorithmus (EEA)

Seien a, b ∈ ℕ. Die Zahlen r_{k} und q_{k} seien wie in (4.7) definiert, dh . (⋆) r_{k} = q_{k+1} · r_{k+1} + r_{k+2} (0 ≤ r_{k+2} < r_{k+1}) Die Folgen (x_{k})_{k≥0} und (y_{k})_{k≥0} seien rekursiv definiert durch 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 r_{k} = x_{k} · a + y_{k} · b für alle k ∈ ℕ_{0} und insbesondere für k = n

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

\underline{Bew:} Die Behauptung läßt sich leicht durch vollständige Induktion nach k ∈ ℕ_{0} beweisen. • Wir wollen jetzt die Definition des ggT’s verallgemeinern:

\underline{(4.9) DEF:} Eine ganze Zahl g heißt größter gemeinsamer Teiler (ggT) von endlich vielen ganzen Zahlen a_{1}, a_{2}, …, a_{n} (n ≥ 2) , wenn gilt: GGT_{0}) g ≥ 0 GGT_{1}) g | a_{i} (∀ i = 1, 2, …, n) GGT_{2}) Für alle t ∈ Z mit t | a_{i} (∀ i = 1, 2, …, n) folgt t | g. Bezeichnung: g = ggT(a_{1}, a_{2}, …, a_{n}) .

\underline{(4.10) SATZ:} Seien a_{1}, a_{2}, …, a_{n} ∈ ℤ (n ≥ 2) . Dann existiert ein eindeutig bestimmter ggT von a_{1}, a_{2}, …, a_{n}, und dieser läßt sich als ganzzahlige Linearkombination von a_{1}, a_{2}, …, a_{n} darstellen.

\underline{Bew:} Die eindeutig bestimmte nichtnegative Zahl g, die das Summenideal

ℤa_{1} + ℤa_{2} + … + ℤa_{n} = { x_{1}a_{1} + x_{2}a_{2} + … + x_{n}a_{n} | a_{1}, a_{2}, …, a_{n} ∈ ℤ }

erzeugt, ist der ggT von a_{1}, a_{2}, …, a_{n}. g ∈ ℤa_{1}+ℤa_{2}+…+ℤa_{n} läßt sich dann aus a_{1}, a_{2}, …, a_{n} ganzzahlig linear kombinieren. •

\underline{(4.11) DEF:} Seien a_{1}, a_{2}, …, a_{n} ∈ ℤ (n ≥ 2) .

a) Die Zahlen a_{1}, a_{2}, …, a_{n} heißen teilerfremd , wenn ggT(a_{1}, a_{2}, …, a_{n}) = 1 gilt.

b) Die Zahlen a_{1}, a_{2}, …, a_{n} heißen paarweise teilerfremd , wenn gilt:

ggT(a_{i}, a_{k}) = 1 ∀ i, k ∈ {1, 2, …, n} mit i ≠ k .

\underline{(4.12) BEM:} a) Die Zahlen a_{1}, a_{2}, …, a_{n} ∈ ℤ sind genau dann teilerfremd, wenn es Zahlen x_{1}, x_{2}, …, x_{n} ∈ ℤ gibt mit x_{1}a_{1} + x_{2}a_{2} + … + x_{n}a_{n} = 1 .

b) Paarweise teilerfremde Zahlen sind auch teilerfremd, aber nicht umgekehrt .

\underline{(4.13) SATZ:} Für a, b, c ∈ ℤ gelten die folgenden Aussagen:

a) a | c und b | c und ggT(a, b) = 1 ⟹ (a · b) | c

b) a | (b · c) und ggT(a, b) = 1 ⟹ a | c.

\underline{BEM:} Ohne die Voraussetzung, daß die Zahlen a und b teilerfremd sind, gelten die obigen Aussagen i.a. nicht: Gegenbeispiel zu a) : 4 | 12 und 6 | 12 , aber 4 · 6 = 24 ist kein Teiler von 12 .

b) 6 | (4 · 9) , aber 6 |̸ 4 und 6 |̸ 9 .

Dual zum Begriff des ggT’s definieren wir jetzt den Begriff des kgV’s .

\underline{(4.14) DEF:} Eine ganze Zahl k heißt kleinstes gemeinsames Vielfaches (kgV) zweier ganzer Zahlen a und b, wenn gilt: KGV_{0}) k ≥ 0 KGV_{1}) a | k und b | k KGV_{2}) Für alle v ∈ Z mit a | v und b | v folgt k | v. Bezeichnung: k = kgV(a, b) .

KGV_{0}) hat die Eindeutigkeit des kgV’s zur Folge (s. Bem. (4.15)). KGV_{1}) besagt, daß k ein gemeinsames Vielfaches von a und b ist. KGV_{2}) bedeutet, daß k Teiler eines jeden gemeinsamen Vielfachen von a und b ist.

\underline{(4.15) BEM:} Zu je zwei ganzen Zahlen a und b gibt es höchstens ein kgV .

\underline{(4.16) SATZ:} Zu je zwei ganzen Zahlen existiert ein eindeutig bestimmtes kgV .

\underline{Bew:} 1) Eindeutigkeit folgt aus (4.15)

2) Existenz Seien a, b ∈ ℤ. Da ℤ ein HIB ist, ist das Ideal ℤa ∩ ℤb ein Hauptideal, d.h. es gibt (genau ein) k ∈ ℕ_{0} mit der Eigenschaft

ℤa ∩ ℤb = ℤk .

KGV_{1}) und KGV_{2}) folgen dann sofort mit Hilfe von (3.17) , d.h.

k = kgV(a, b) .
•

(4.17) LEMMA:

Rechenregeln für das kgV

Für alle a, b ∈ ℤ gilt:

a) kgV(a, b) = kgV(b, a)  b) kgV(a, b) = | a | ⟺ b | a
c) kgV(a, 0) = 0  d) kgV(0, 0) = 0
e) kgV(a, b) = 0 ⟺ (a = 0 ∨ b = 0) f) kgV(a, b) = kgV(| a |, | b |)

\underline{(4.18) BEM:} Für beliebige ganze Zahlen a, b bezeichne GV^{+}(a, b) := V^{+}(a) ∩ V^{+}(b) ⊆ ℕ_{0} die Menge der nichtnegativen gemeinsamen Vielfachen von a und b. Es sei k := kgV(a, b) . Im Falle a = 0 oder b = 0 ist 0 = k = min(GV^{+}(a, b), ≤) . Im Falle a ≠ 0 und b ≠ 0 ist dagegen k > 0 und deshalb

k := min((GV^{+}(a, b) ∩ ℕ, ≤)) .

Für alle a, b ∈ ℤ gilt aber k = min((GV^{+}(a, b), |)) .

\underline{(4.19) DEF:} a_{1}, a_{2}, …, a_{n} (n ≥ 2) seien ganze Zahlen. Eine ganze Zahl k heißt kleinstes gemeinsames Vielfaches (kgV) von a_{1}, a_{2}, …, a_{n}, wenn gilt: KGV_{0}) k ≥ 0 KGV_{1}) a_{1} | k , a_{2} | k , …, a_{n} | k KGV_{2}) Für alle v ∈ ℤ mit a_{1} | v , a_{2} | v , …, a_{n} | v folgt k | v. Bezeichnung: k = kgV(a_{1}, a_{2}, …, a_{n})

\underline{(4.20) SATZ:} Zu je n ganzen Zahlen existiert immer ein eindeutig bestimmtes kgV .

\underline{Bew:} Die Zahl k ∈ ℕ_{0} mit ℤa_{1} ∩ ℤa_{2} ∩ … ∩ ℤa_{n} = (k) ist kgV von a_{1}, a_{2}, …, a_{n}. •

\underline{(4.21) BEM:} Sind r_{1} = \frac{a_{1}}{b_{1}} , r_{2} = \frac{a_{2}}{b_{2}} , …, r_{n} = \frac{a_{n}}{b_{n}} rationale Zahlen, so ist ihr Hauptnenner gerade das kgV der einzelnen Nenner b_{1}, b_{2}, …, b_{n}. Diese Bildung ist wichtig für die Addition rationaler Zahlen. Ist k = kgV(b_{1}, b_{2}, …, b_{n}) und gilt b_{i} · c_{i} = k für alle i = 1, 2, …, n, so folgt

r_{1} + r_{2} + … + r_{n} = \frac{a_{1}}{b_{1}} + \frac{a_{2}}{b_{2}} + … + \frac{a_{n}}{b_{n}} = \frac{a_{1} · c_{1} + a_{2} · c_{2} + … + a_{n} · c_{n}}{k} .

Zum Abschluß untersuchen wir den Zusammenhang zwischen dem ggT und dem kgV zweier ganzer Zahlen:

\underline{(4.22) SATZ:} Für ganze Zahlen a und b gilt

ggT(a, b) · kgV(a, b) = | a · b | .

\underline{Bew:} Es genügt, die Behauptung für a > 0 und b > 0 zu beweisen. Ist k = kgV(a, b) , so folgt k | a · b . Für den zu k komplementären Teiler g von a · b läßt sich g = ggT(a, b) zeigen. Folglich gilt g · k = a · b. •

\underline{(4.23) BEM:} Berechnungsverfahren für das kgV Sind a und b ganze Zahlen , für die ggT(a, b) ≠ 0 gilt, so folgt

kgV(a, b) = \frac{| a · b |}{ggT(a, b)} ,

wobei sich ggT(a, b) (leicht!) mit Hilfe des euklidischen Algorithmus berechnen läßt .