ggT und kgV
Zu zwei oder mehr Zahlen werden der größte gemeinsame Teiler, das kleinste gemeinsame Vielfache und ihre Teilermengen bestimmt.
Der ggT ist das größte Element im Durchschnitt 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 im Durchschnitt 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:
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}
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;