Pascal-Toolbox Nr. 7

Berechnung des größten gemeinsamen Teilers (ggT) nach dem Euklidischen Algorithmus

Für viele mathematische Berechnungen kann es zweckmäßig sein, den größten gemeinsamen Teiler von zwei Zahlen zu wissen. Wir werden die Berechnung auf dieser Seite anhand des Euklidischen Algorithmus studieren und eine Umsetzung in Pascal erstellen.

Schematische Darstellung des Algorithmus

Die Variable n enthält hiernach den ggT von m und n. Voraussetzung: m ist größer-gleich n und m,n sind Elemente der natürlichen Zahlen (d.h. ganz und >0)

Beschreibung des Algorithmus

Der Algorithmus liefert zu gegebenen m, n aus der Menge der natürlichen Zahlen, m größer-gleich n, den größten gemeinsamen Teiler ggT(m,n).

1. Teile m durch n und bestimme den Rest r (d.h. bestimme r, so daß gilt m=q * n + r, wobei q, r Elemente der Menge der ganzen Zahlen sind mit r größer-gleich 0 und kleiner n).
2. Falls r=0 gilt, ist man fertig, und das Ergebnis ist der Wert von n.
3. Andernfalls: Setze m=n und n=r und gehe zu (1).

Beweis des Algorithmus

Daß der Euklidische Algorithmus tatsächlich den ggT(m,n) berechnet, läßt sich wie folgt einsehen:

Ist r > 0, so wird in (3) die Anweisung m=n und n=r ausgeführt und anschließend zu (1) gesprungen. Dies bedeutet, daß man die Aufgabe, den ggT(m,n) zu berechnen, durch die Aufgabe, den ggT(n,r) zu berechnen ersetzt hat; dies ist aber genau der gleiche Wert wie ggT(m,n) (Beweis folgt weiter unten). Ist r=0, so gilt m=q * n, d.h. n ist ein Teiler von m; also ist in diesem Fall n der größte gemeinsame Teiler von m und n.

Beweis für ggt(m,n)=ggt(n,r)

Feststellung:
Wenn b sowohl Teiler von a1 als auch von a2 ist, dann teilt b auch (c1*a1 + c2*a2) für beliebige c1,c2.
(Kurzschreibweise: wenn b|a1 und b|a2, dann b|(c1*a1+c2*a2))

Nachweis:
a1=b*t1
a2=b*t2

Beide Gleichungen werden mit c1 bzw. c2 erweitert:
a1*c1=b*t1*c1
a2*c2=b*t2*c2

Wir setzen r1=t1*c1, r2=t2*c2. Es folgt:
a1*c1=b*r1
a2*c2=b*r2

Durch Addition der beiden Gleichungen erhalten wir:
a1*c1+a2*c2=b*r1+b*r2
umgeformt:
a1*c1+a2*c2=b*(r1+r2)

Damit ist bewiesen, daß die Feststellung gilt. b muß mit (r1+r2) multipliziert werden, um den Zielwert zu erhalten.

Es gelte m=q*n+r. Ist t ein gemeinsamer Teiler von n und r, so ist aufgrund des zuvor Bewiesenen t auch ein gemeinsamer Teiler von m und n. Ist umgekehrt t ein gemeinsamer Teiler von m und n, so ist (aufgrund des zuvor Bewiesenen und wegen r=m-q*n) t auch ein gemeinsamer Teiler von n und r. Die Menge der gemeinsamen Teiler von n und r ist also gleich der Menge der gemeinsamen Teiler von m und n; insbesondere gilt also ggT(n,r)=ggT(m,n).

q.e.d.

Umsetzung des Algorithmus in Pascal

Eine einfache Umsetzung des Algorithmus wäre die folgende:

...

  while (n>0) do

  begin

    z:=n;

    n:=m mod n;

    m:=z;

  end;

...

Hier enthält - entgegengesetzt zur oben aufgeführten Anleitung - m den Wert für den ggT(m,n).

Setzt man dies in eine Funktion um, sieht diese wie folgt aus:

function ggT(m,n:integer):integer;

var z:integer;

begin

 while (n>0) do

  begin

    z:=n;

    n:=m mod n;

    m:=z;

  end;

  ggT:=m;

end;

So, das sollte es eigentlich gewesen sein. Viel Spaß damit!

Alle Angaben ohne Gewähr.