ggT und kgV
Je zwei von Null verschiedene ganze Zahlen besitzen jeweils nur endlich viele Teiler, sodass es einen größten gemeinsamen Teiler gibt. Genauer definieren wir:
Definition (größter gemeinsamer Teiler, teilerfremd, relativ prim)
Seien a, b ganze Zahlen, die nicht beide 0 sind. Dann setzen wir
ggT(a, b) = maxd ≥ 1 (d | a und d | b).
Weiter setzen wir ggT(0, 0) = 0. Die Zahl ggT(a, b) heißt der größte gemeinsame Teiler von a und b. Zwei ganze Zahlen a und b heißen teilerfremd oder relativ prim, falls ggT(a, b) = 1. Wir schreiben auch (a, b) statt ggT(a, b).
Die Notation (a, b) ist nicht ganz ungefährlich, da auch geordnete Paare so bezeichnet werden. Solange keine Verwechslungsgefahr besteht, ist die Klammernotation aber oftmals deutlich übersichtlicher.
Eine bekannte Anwendung des ggT ist das Kürzen von Brüchen: Ist a/b ∈ ℚ mit a, b ≠ 0 und d = (a, b), so ist a′/b′ mit a′ = a/d und b′ = b/d der gekürzte Bruch. Es gilt a/b = a′/b′ und die Zahlen a′ und b′ sind relativ prim.
Der ggT lässt sich geometrisch mit Hilfe von Rechtecksflächen visualisieren:
Geometrische Interpretation von ggT(12, 30) = 6
Weiter definieren wir:
Definition (kleinstes gemeinsames Vielfaches)
Seien a, b ganze von 0 verschiedene Zahlen. Dann setzen wir
kgV(a, b) = minc ≥ 1 (a | c und b | c).
Weiter setzen wir kgV(0, a) = kgV(a, 0) = 0 für alle ganzen Zahlen a. Die Zahl kgV(a, b) heißt das kleinste gemeinsame Vielfache von a und b. Wir schreiben auch [ a, b ] statt kgV(a, b).
In den meisten Anwendungen ist a, b ≠ 0 oder sogar a, b ≥ 1. Wir nehmen die Fälle a = 0 und b = 0 mit auf, damit (a, b) und [ a, b ] für alle ganzen Zahlen erklärt sind. Wir werden sehen, dass die Operationen den Charakter eines Durchschnitts bzw. einer Vereinigung haben.
Beide Definitionen lassen sich leicht auf mehr als zwei Zahlen verallgemeinern. Dadurch ist der größte gemeinsame Teiler ggT(a1, …, an) und das kleinste gemeinsame Vielfache kgV(a1, …, an) von a1, …, an definiert. Erneut verwenden wir auch die vereinfachten Notationen (a1, …, an) und [ a1, …, an ].
Beispiele
(1) | (6, −15) = 3, (4, 0) = 4, (2, 5) = 1, 2 und 5 sind relativ prim, |
(2) | (4, 8, 10) = 2, (3, 7, 9, 0) = 1, |
(3) | [ 3, 5 ] = 15, [ 4, 12 ] = 12, [ 0, 1 ] = [ 1, 0 ] = [ 0, 0 ] = 0, |
(4) | [ 2, 3, 15 ] = 30, [ 10, 8, 0 ] = 0. |
ggT(a, b) für a, b = 1, …, 20. Die 1-Einträge markieren teilerfremde Paare.
Für alle a, b ∈ ℤ gilt (a, b) | a, (a, b) | b, (a, b) ≤ max(| a |, | b |). Für a ≠ 0 gilt (a, b) ≤ | a |. Analoges gilt für b, sodass (a, b) ≤ min(|a|, | b |) für a, b ≠ 0. Weitere Eigenschaften des ggT sind:
Satz (Eigenschaften des ggT)
Für alle ganzen Zahlen a, b, c, d, e, n, m gilt:
| (G1) | (a, a) = (0, a) = |a|, |
| (G2) | (a, b) = (b, a) = (|a|, |b|), |
| (G3) | a | b genau dann, wenn (a, b) = |a|, |
| (G4) | a ≠ 0 impliziert (a, b) ≤ (a, na + mb), |
| (G5) | (a, b) = (a, na + b), speziell (a, b) = (a, b − a) = (a − b, b), |
| (G6) | e | a und e | b impliziert e | (a, b), |
| (G7) | (ca, cb) = |c| (a, b), |
| (G8) | d | ab und (d, a) = 1 impliziert d | b, |
| (G9) | a | c, b | c und (a, b) = 1 impliziert ab | c, |
| (G10) | (a, c) = 1 und (b, c) = 1 impliziert (ab, c) = 1. |
Beweis
Die ersten fünf Eigenschaften folgen aus der Definition und den elementaren Eigenschaften der Teilbarkeitsrelation. Die anderen Eigenschaften lassen sich mit Hilfe der Eindeutigkeit der Primfaktorzerlegung leicht einsehen. Exemplarisch beweisen wir die Eigenschaft (G8) für a, b, d ≥ 1:
Sei d ein Teiler von ab. Dann gilt
exp(d) ≤ exp(ab) = exp(a) + exp(b) für alle Primzahlen p.
Ist nun (d, a) = 1, so gilt exp(a) = 0 für alle Primteiler p von d. Hieraus folgt
exp(d) ≤ 0 + exp(b) = exp(b) für alle Primteiler p von d.
Dies zeigt, dass d | b.
Anschaulicher formuliert lautet der Beweis von (G8) einfach: Ist d ein Teiler des Produkts ab und teilerfremd zu a, so ist die PFZ von d in der PFZ von b enthalten, sodass d ein Teiler von b ist.
Die folgende Aussage ist ein Spezialfall von (G8):
Ist p prim und p | ab, so gilt p | a oder p | b.(Teilbarkeitssatz von Euklid)
Teilt eine Primzahl also ein Produkt zweier Zahlen, so teilt sie einen Faktor. Diese keineswegs triviale Aussage spielt beim klassischen Beweis der Eindeutigkeit der Primfaktorzerlegung eine Schlüsselrolle, denn aus der Verallgemeinerung des Teilbarkeitssatzes auf mehr als zwei Faktoren lässt sich die Eindeutigkeit der Primfaktorzerlegung leicht gewinnen. Der Teilbarkeitssatz selbst muss direkt bewiesen werden. Wir diskutieren dies in den Übungen.
Für das kgV gelten analoge Eigenschaften. Wir verzichten hier auf eine Liste, notieren aber exemplarisch die zur Eigenschaft (G6) analoge Eigenschaft:
Für alle a, b, c gilt: a | c und b | c impliziert kgV(a, b) | c.
Das kgV ist also die minimale multiplikative Verschmelzung zweier Zahlen.
Liegen Primfaktorzerlegungen der beteiligten Zahlen vor, so lassen sich die beiden Größen ggT und kgV leicht ablesen:
Beispiele
Für a = 171500 und b = 907500 gilt:
| a | = 23 · 54 · 73 | = 23 · 30 · 54 · 73 · 110 |
| b | = 22 · 31 · 54 · 112 | = 22 · 31 · 54 · 70 · 112 |
| (a, b) | = 22 · 54 | = 22 · 30 · 54 · 70 · 110 = 2500 |
| [ a, b ] | = 23 · 31 · 54 · 73 · 112 | = 23 · 31 · 54 · 73 · 112 = 622545000 |
Kurz:
Bilde Minima bzw. Maxima in den Exponenten.
Die formale Fassung dieser Überlegung lautet:
Satz (Bestimmung von ggT und kgV über die PFZ)
Für alle a, b ≥ 1 gilt:
(a, b) = ∏p prim pmin(exp(a), exp(b)), [ a, b ] = ∏p prim pmax(exp(a), exp(b)).
Hieraus gewinnen wir:
Korollar (Produktsatz)
Für alle a, b gilt |a b| = (a, b) [ a, b ].
Beweis
Es genügt, die Aussage für a, b ≥ 1 zu beweisen. Für a, b ≥ 1 gilt aber
| a b | = ∏p prim pexp(a) ∏p prim pexp(b) = ∏p prim pexp(a) + exp(b) |
| = ∏p prim pmin(exp(a), exp(b)) + max(exp(a), exp(b)) | |
| = ∏p prim pmin(exp(a), exp(b)) ∏p prim pmax(exp(a), exp(b)) | |
| = (a, b) [ a, b ]. |