Skript zu: Einfuehrung in die Informatik I: ggT (1)

ggT: größter gemeinsamer Teiler (1)

Wir fragen nach einem Verfahren, den größten gemeinsamen Teiler ggT(a,b) von zwei natürlichen Zahlen a und b zu berechnen. Das aus dem Gymnasium bekannte Verfahren verwendet die Primzahlen, die wir nicht bequem zur Verfügung haben; wir machen deshalb einen direkten Ansatz. Es kommt uns ohnehin nicht auf die Lösung des Problems an (die ist schon seit 2000 Jahren bekannt), sondern auf den Lösungsweg , der womöglich lehrreich ist.

Wir beginnen mit einigen einfachen mathematischen Beobachtungen. Wir stellen fest:

wenn a einen Teiler d hat, also xN : a = x*d, dann hat auch jedes Vielfache n*a den Teiler d: n*a = (n*x)*d
alle Vielfachen von d haben den Teiler d, und d ist die kleinste Zahl davon
wenn a und b den Teiler d haben, dann hat ihn auch jede Linearkombination davon: sei a = x*d, b = y*d, so ist m*a + n*b = (m*x + n*y)*d
wenn eine Zahl c den Teiler d hat, so ist d <= c
die Menge der ganzzahligen positiven Linearkombinationen von a und b ist nicht leer und hat also ein kleinstes Element, das den Teiler d hat
dies gilt für alle gemeinsamen Teiler von a und b

Daraus ergibt sich nun:

der größte gemeinsame Teiler von zwei gegebenen Zahlen a und b ist deren kleinste positive Linearkombination

Wir suchen nun durch systematisches Subtrahieren möglichst kleine Kombinationen aufzubauen; das ist korrekt, weil eine Linearkombination von Linearkombinationen wieder eine Linearkombination der Ausgangswerte ist. Kommen wir dabei zum Ende, so haben wir wegen ggT(n,n) = n den gesuchten Wert gefunden; und wir müssen zum Ende kommen, weil unsere Zahlen immer kleiner werden. So kommen wir auf das Verfahren:

PROCEDURE ggT(a, b: CARDINAL): CARDINAL;
(* PRE: a>0, b>0 *)
BEGIN IF a=b THEN RETURN a
      ELSIF a>b THEN RETURN ggT(a-b, b)
      ELSE RETURN ggT(b-a, a)
      END
END ggT;

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 20. März 2000, 17:41