Algebra

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;
      

Siehe auch:

Wikipedia: Größter gemeinsamer Teiler
www.matheass.de