Der "Euklidische Algorithmus" (EA) ist ein Verfahren zur Bestimmung des ggT zweier Zahlen, welches schon Euklid vor 2200 Jahren in seinem bekannten Mathematikwerk beschreibt. Dieses Rechtsverfahren erwies sich als sehr tiefgehend und praktisch. Beginnen wir wieder mit einem Beispiel:
gesucht sei ggT(969,627)
969=1·627+342
627=1·342+285
342=1·285+57
285=5·57+0
Damit ist man fertig: ggT(969,627)=57
Warum funktioniert dieses Verfahren? Worauf beruht es? Eigentlich ist dafür nur eine einfache, bereits bekannte Regel verantwortlich:
(T6) aïb und aïb
±c Þa
ïc
(Kapitel 1; Satz 1.1 (T6))
Ist nun d der ggT von 969 und 627=969-
342, so ist d nach (T6) auch ein Teiler von 342. Da aber d schon der größte gemeinsame Teiler von 969 und 627 ist, muß er auch der größte gemeinsame Teiler von 627 und 342 sein. Mit dem selben Schluß ist dann aber d auch Teiler von 285, da ja d gemeinsamer Teiler von 627 und 342 ist. So schließt man weiter, bis der Rest r 0 wird (was ja notwendig einmal eintreten muß). d muß also auch ein gemeinsamer Teiler von 57 und 0 sein. Welches ist aber der größte gemeinsame Teiler von 57 und 0 - natürlich 57. Also ist rückwärts geschlossen 57 auch der größte gemeinsame Teiler von 969 und 627.
Es gilt also ggT(a,b)=ggT(a-b,b).
Wenden wir auf den Ausdruck rechts dieselbe Regel an, so ergibt sich
ggT(a-b,b)=ggT((a-b)-b),b)=ggT(((a-b)-b)-b,b)=...=ggT(r,b),
wobei r der Rest von a bei Division durch b ist (a=k×
b+r mit 0£
r<b). Wir können als auch direkt schreiben ggT(a,b)=ggT(a-k×
b,b)=ggT(r,b)=ggT(b,r)
Beschreiben wir nun den EA noch einmal allgemein:
gesucht ggT(a,b):
a=k1·b+r1 ,r1<b
b=k2·r1+r2 ,r2<r1
r1=k3·r2+r3 ,r3<r2
..........................
rn-2=kn·rn-1+rn ,rn<rn-1
rn-1=kn+1·
rn+0 Þ ggT(a,b)=rn
Dieses Verfahren ist endlich, da die Zahlen a, b, r1 usw. immer kleiner werden.
Und noch ein Beispiel: ggT(130900,33957):
130900=3×
33957+29029
33957=1×
29029+4928
29029=5×
4928+4389
4928=1×
4389+539
4389=8×
539+77
539=7×
77+0 Þ
ggT(130900,33957)=77
Übrigens gibt es eine merkwürdige Abschätzung für die Anzahl der Schritte beim EA: Ist b die kleinere der beiden Zahlen, so ist die Anzahl der Schritte immer kleiner als das Fünffache der Anzahl der Ziffern von b. Vergleiche dies mal bei den folgenden Aufgaben
AUFGABE 2.6
Berechne den ggT der folgenden Zahlen mit dem EA:
a) 3059; 646 b) 4081; 2585 c) 2112; 836 d) 1597; 987
| Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zur Bestimmung des ggT starten. |
|
Ein für uns sehr wichtiges Ergebnis liefert der folgende Satz 2.1. Vorher wollen wir aber noch eine Bezeichnung einführen, die der Vektoralgebra entlehnt ist: Sind x und y zwei Zahlen oder Variable, so heißt rx+sy eine "Linearkombination" von x und y.
SATZ 2.1
(Lemma von Bachet)
Ist d=ggT(a,b), so gibt es k,lÎ
Z mit ka+lb=d.
Beweis: Zum Beweis benutzen wir :
Sind sa+tb=c und ua+vb=d zwei Linearkombinationen von a und b, so ist auch die Summe c+d=(s+u)a+(t+v)b wieder eine Linearkombination von a und b. Beginnen wir nun mit
a=1×
a+0×
b und
b=0×
a+1×
b und wenden auf die linke Seite den EA an, so endet dieser mit dem ggT(a,b), während rechts eine Linearkombination von a und b steht.
Wir demonstrieren dies am ersten Beispiel:
| Euklid | Berlekamp | |
| 969= 1·627+342 | 969= 1·969+0·627 | |
| 627= 1.342+285 | 627= 0·969+1·627 | |
| 342= 1·285+57 | 342= 1·969- 1·627 | |
| 285= 5·57+0 | 285=-1·969+2·627 | |
| 57=2·969- 3·627 |
Damit haben wir zwei Zahlen k und l gefunden mit k× 969+l×627=ggT(969,627).
Als weiteres Beispiel führen wir das zweite von oben an:
130900= 1·130900+0·33957
33957= 0·130900+1·33957 ï·3
29029= 1·130900- 3·33957
4928=-1·130900+4 ·33957
ï·5
4389= 6·130900-23·33957
539=-7·
130900+27·33957 ï·8
77=62·130900-239·33957
Der nächste Schritt führt auf
0=.......... , also ist der EA beendet.
Wir haben also die Zahlen k=62 und l=-239 gefunden, mit denen gilt k·130900+l· 33957=ggT(130900,33957)=77
Eine Formalisierung dieses Verfahrens ist unter dem Namen Berlekamp-Algorithmus (BA) bekannt.
Wir definieren vier Folgen an, xn, yn und qn nach folgendem Schema ([r] bedeutet im Folgenden die sogenannte Gaußklammer, also den ganzzahligen Anteil von r):
| a1=a | x1=1 | y1=0 | q1=0< |
| a2=b | x2=0 | y2=1 | q2=[a1/a2] |
| a3=a1-q2·a2 | x3=x1-q2·x2 | y3=y1-q2y2 | q3=[a2/a3] |
| ........... | ........... | ........... | ........... |
| ai+1=ai-1-qi·ai | xi+1=xi-1-qi·xi | yi+1=yi-1-qi·yi | qi+1=[ai/ai+1] für i>2 |
Beispiele: a=91; b=56
| i | ai | xi | yi | qi |
| 1 | 91 | 1 | 0 | 0 |
| 2 | 56 | 0 | 1 | 1 |
| 3 | 35 | 1 | -1 | 1 |
| 4 | 21 | -1 | 2 | 1 |
| 5 | 14 | 2 | -3 | 1 |
| 6 | 7 | -3 | 5 | 2 |
| 7 | 0 | - | - | - |
also: -3·91+5·56=7=ggT(891,56)
a=9111, b=47
| i | ai | xi | yi | qi |
| 1 | 9111 | 1 | 0 | 0 |
| 2 | 47 | 0 | 1 | 193 |
| 3 | 40 | 1 | -193 | 1 |
| 4 | 7 | -1 | 194 | 5 |
| 5 | 5 | 6 | -1163 | 1 |
| 6 | 2 | -7 | 1357 | 2 |
| 7 | 1 | 20 | -3877 | 2 |
| 8 | 0 | - | - | - |
also:20·9111-3877·47=1=ggT(9111,47)
AUFGABE 2.7
Bestimme mit dem Berlekamp-Algorithmus die Zahlen k und l in k·a+l·b=ggT(a,b):
a) a=286, b=121 b) a=9111, b=47 c) a=391, b=153
d) a=235, b= 3567 e) a=257, b=267 f) a=322, b=199
g) a=7989, b=1233 h) a=567, b=568
| Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zum Berlekamp-Algorithmus starten. | |
AUFGABE 2.8
Zeige, daß man in Satz 2.1 k durch k+rb ersetzen kann, wenn man gleichzeitig l durch l-ra ersetzt. Gib dann zu jeder der Aufgaben aus Aufgabe 2.7 drei neue Lösungen an.
AUFGABE 2.9
Zeige, daß man jede ganze Zahl c als Linearkombination von teilerfremden Zahlen a und b angeben kann.
Löse dieses Problem speziell für a=7, b=11 und c=15 sowie für a=33, b= 29 und c=100.
Download Kap_2 (63 KB)
