ggT und kgV
Zu zwei oder mehr positiven ganzen Zahlen werden der größte gemeinsame Teiler, das kleinste gemeinsame Vielfache und ihre Teilermengen bestimmt.
Der ggT ist das größte Element in der Schnittmenge der Teilermengen von a und b. In der Bruchrechnung ist der ggT von Zähler und Nenner die größte Zahl, mit der der Bruch gekürzt werden kann.
Das kgV ist das kleinste Element in der Schnittmenge der Vielfachenmengen von a und b. In der Bruchrechnung bezeichnet man das kgV zweier Nenner als den Hauptnenner.
Hat man den ggT(a,b) bereits bestimmt, so erhält man das kgV(a,b) nach der Formel
kgV(a,b) = a·b / ggT(a,b)
Beispiel 1:
a = 24
b = 256
größter gemeinsamer Teiler ggT = 8
kleinstes gemeinsames Vielfaches kgV = 768
Teilermengen:
T(a) = { 1 2 3 4 6 8 12 24}
T(b) = { 1 2 4 8 16 32 64 128 256}
T(a) ∩ T(b) = { 1 2 4 8}
Beispiel 2:
a = 195
b = 234
c = 273
größter gemeinsamer Teiler ggT = 39
kleinstes gemeinsames Vielfaches kgV = 8190
Teilermengen:
T(a) = { 1 3 5 13 15 39 65 195}
T(b) = { 1 2 3 6 9 13 18 26 39 78 117 234}
T(c) = { 1 3 7 13 21 39 91 273}
T(a) ∩ T(b) ∩ T(c) = { 1 3 13 39}
Beispiel 3:
Zusätzlich werden die Summe aller Teiler σ(n) und die Summe der echten Teiler σ*(n) bestimmt.
Zahlen, die gleich der Summe ihrer echten Teiler sind, nennt man vollkommene Zahlen.
a = 6
b = 28
c = 496
d = 8128
e = 33550336
f = 8589869056
g = 137438691328
Größter gemeinsamer Teiler ggT = 2
Kleinstes gemeinsames Vielfaches kgV = 1,21993659586792E25
Teilermengen :
T(a) = { 1 2 3 6 }
T(b) = { 1 2 4 7 14 28 }
T(c) = { 1 2 4 8 16 31 62 124 248 496 }
T(d) = { 1 2 4 8 16 32 64 127 254 508 1016 2032 4064 8128 }
T(e) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16382 32764 65528 131056 262112 524224 ... }
T(f) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262142 524284 ... }
T(g) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524287 ... }
T(a) ∩ T(b) ∩ T(c) ∩ T(d) ∩ T(e) ∩ T(f) ∩ T(g) = { 1 2 }
Teilersummen :
σ(a) = 12 σ*(a) = 6 vollkommene Zahl
σ(b) = 56 σ*(b) = 28 vollkommene Zahl
σ(c) = 992 σ*(c) = 496 vollkommene Zahl
σ(d) = 16256 σ*(d) = 8128 vollkommene Zahl
σ(e) = 67100672 σ*(e) = 33550336 vollkommene Zahl
σ(f) = 17179738112 σ*(f) = 8589869056 vollkommene Zahl
σ(g) = 274877382656 σ*(g) = 137438691328 vollkommene Zahl
Die erste Hälfte der Teilermenge bildet offenbar jedesmal die Folge der Potenzen von 2.
(Siehe auch Primfaktorzerlegung)
Verfahren
Der größte gemeinsame Teiler zweier Zahlen kann aus ihren Primfaktorzerlegungen ermittelt werden. Ist bei großen Zahlen aber die Primfaktorzerlegung nur schwer zu ermitteln, hilft der nach Euklid benannte Algorithmus weiter.
Euklid nutzte aus, dass sich der ggT zweier Zahlen nicht ändert, wenn man die kleinere von der größeren abzieht. Heute verwendet man statt dem Subtraktionsalgorithmus meist den schnelleren Divisionsalgorithmus, bei dem die Differenz der Zahlen durch den Rest bei der Division ersetzt wird.
Divisionsalgorithmus in PASCAL:
function ggT(a,b:integer):integer;
var
r: integer;
begin
repeat
r := a mod b;
a := b;
b := r;
until r=0;
result := a;
end;