Größter gemeinsamer Teiler
Von fundamentaler Bedeutung für alles Weitere ist folgende Begriffsbildung:
Definition (größter gemeinsamer Teiler, ggT(a, b))
Seien a, b nicht beide Null. Dann heißt die größte Zahl d ≥ 1, die sowohl ein Teiler von a als auch ein Teiler von b ist, der größte gemeinsame Teiler von a und b, in Zeichen d = ggT(a, b). Wir setzen weiter ggT(0, 0) = 0.
Sind a und b nicht beide gleich Null, so existiert ein d ≥ 1 wie in der Definition in der Tat. Denn 1 ist ein gemeinsamer Teiler von a und b, und jeder weitere positive gemeinsame Teiler d von a und b ist kleinergleich |a| oder kleinergleich |b|. Es gibt also nur endlich viele gemeinsame Teiler d ≥ 1 von a und b, und einer von ihnen ist der größte. Wir werden unten ein Verfahren zur effektiven Bestimmung von ggT(a, b) kennen lernen.
Da jede Zahl die Null teilt, existiert kein wörtlicher größter gemeinsamer Teiler für die Wahl a = b = 0. Die Setzung von ggT(0, 0) = 0 ist aber notationell bequem und sinnvoll. So gilt z. B. ggT(a, a) = |a| für alle a.
Es gilt zum Beispiel
ggT(2, 5) = 1, ggT(10, 12) = 2, ggT(− 6, 9) = 3, ggT(− 4, − 8) = 4.
Allgemein gilt:
Satz (Eigenschaften des größten gemeinsamen Teilers)
Für alle a, b, c, n, m gilt:
(G1) ggT(a, a) = ggT(0, a) = |a|,
(G2) ggT(a, b) = ggT(b, a) = ggT(|a|, |b|),
(G3) a|b gdw ggT(a, b) = |a|,
(G4) ggT(a, b) ≤ ggT(a, na + mb),
(G5) ggT(a, b) = ggT(a, na + b).
Der Beweis dieser Eigenschaften kann wieder dem Leser überlassen bleiben. Wir bemerken aber noch, dass die Ungleichung in (G4) im Allgemeinen keine Gleichung ist. Denn es gilt
ggT(2, 3) = 1, aber ggT(2, 1 · 2 + 2 · 3) = ggT(2, 8) = 2.
In Analogie zur Definition des größten gemeinsamen Teilers definieren wir:
Definition (kleinstes gemeinsames Vielfaches, kgV(a, b))
Seien a, b ≠ 0. Dann heißt die kleinste Zahl v ≥ 1, die sowohl ein Vielfaches von a als auch ein Vielfaches von b ist, das kleinste (positive) gemeinsame Vielfache von a und b, in Zeichen v = kgV(a, b). Weiter setzen wir kgV(0, a) = kgV(a, 0) = 0 für alle a.
Es gilt kgV(a, b) ≤ |a b|. Als Anwendung der Division mit Rest zeigen wir:
Satz (Teilereigenschaft des kgV)
a|w und b|w impliziert kgV(a, b)|w.
Beweis
Die Aussage ist klar für w = 0, da dann c|w für alle c gilt. Sei also w ≠ 0.
Sei v = kgV(a, b). Wegen w ≠ 0 ist v ≥ 1. Sei also w = q v + r mit 0 ≤ r < v.
Dann gilt r = w − q v, und damit a|r und b|r nach (T7). Also ist r ein gemeinsames Vielfaches von a und b. Wegen r < v = kgV(a, b) ist dann aber r = 0. Folglich gilt w = q v und damit v|w.
Damit können wir nun weitere Eigenschaften der ggT-Funktion beweisen:
Satz (weitere Eigenschaften des größten gemeinsamen Teilers)
Für alle a, b, c, … gilt:
| (G6) | e|a und e|b impliziert e|ggT(a, b), |
| (G7) | ggT(ca, cb) = |c| ggT(a, b), |
| (G8) | d|ab und ggT(d, a) = 1 impliziert d|b, |
| (G9) | a|c, b|c und ggT(a, b) = 1 impliziert ab|c, |
| (G10) | ggT(a, c) = 1 und ggT(b, c) = 1 impliziert ggT(ab, c) = 1. |
Beweis
zu (G6): Sei d = ggT(a, b). Die Aussage ist klar für d = 0 oder e = 0.
Seien also d, e ≠ 0, und sei v = kgV(e, d) ≥ 1. Dann ist a ein Vielfaches von e und von d, also gilt v|a. Ebenso gilt v|b. Damit ist also v ein gemeinsamer Teiler von a und b, also d ≥ v = kgV(e, d) ≥ d. Folglich ist v = d, und damit e|d.
zu (G7): Seien d = ggT(a, b) und d′ = ggT(ca, cb). O. E. seien a, b ≠ 0 und c > 0. Wegen cd|ca und cd|cb gilt cd ≤ d′. Wegen c|ca und c|cb gilt c|d′ nach (G6). Also gibt es ein e mit d′ = ce. Dann gilt ce|ca und ce|cb, also e|a und e|b. Dann ist aber e ≤ d und damit d′ = ce ≤ cd.
zu (G8): Es gilt d|bd und d|ba. Nach (G6) gilt also d|ggT(bd, ba). Aber ggT(bd, ba) = |b| · ggT(d, a) = |b|. Also d|b.
zu (G9): Sei v = kgV(a, b) ≤ |a b|, und sei v = e b. Dann gilt a|e b und ggT(a, b) = 1, also a|e nach (G8). Also ist v ≥ |a b|, und damit v = |a b|.
Da c ein Vielfaches von a und b ist, gilt v|c und damit ab|c.
zu (G10): Sei d ≥ 1 ein Teiler von ab und c. Wir zeigen, dass d = 1 gilt.
Wegen ggT(a, c) = 1 und d|c gilt ggT(d, a) = 1. Wegen d|ab gilt dann aber d|b nach (G8). Wegen ggT(b, c) = 1 und d|c ist dann aber d = 1.
Analog zu (G7) gilt
(#) kgV(c a, c b) = |c| kgV(a, b) für alle a, b, c.
Denn |c| kgV(a, b) ist ein Vielfaches von c a und c b, und deswegen gilt „≤“. Zum Beweis von „≥“ sei kgV(c a, c b) = c d. O. E. ist c d ≠ 0. Dann gilt c a|c d und c b|c d, also a|d und b|d. Folglich gilt kgV(a, b)|d und damit c · kgV(a, b)|kgV(c a, c b).
Damit können wir auch folgenden ansprechenden Zusammenhang beweisen:
Satz (Produktsatz für ggT und kgV)
Für alle a, b gilt: |a · b| = ggT(a, b) · kgV(a, b).
Beweis
Sei d = ggT(a, b). Die Aussage ist klar für d = 0. Ist d = 1, so ist kgV(a, b) = |a b| wie im Beweis von (G9) oben. Sei also d ≥ 1, und seien a = d a′ und b = d b′. Dann ist ggT(a′, b′) = 1 und damit gilt mit (#):
|a b| = d2 |a′ b′| = d · d · kgV(a′, b′) = ggT(a, b) · kgV(d a′, d b′) = ggT(a, b) · kgV(a, b).
Unsere Untersuchungen der Teilbarkeit sind nun so weit gediehen, dass der Leser an dieser Stelle zu den Abschnitten über Primzahlen und der Eindeutigkeit der Primfaktorzerlegung springen kann, wenn er möchte. Die natürliche Fortsetzung scheint aber an dieser Stelle die Diskussion eines Verfahrens zu sein, das den größten gemeinsamen Teiler zweier Zahlen effektiv ermittelt.