Der
Euklidische Algorithmus
 |
 |
 |
Mathematik
Didaktik Seminar
Didaktik Seminar
|
Der
Euklidische Algorithmus
|
|
Mathematik
Didaktik Seminar |
Der Euklidische Algorithmus
| Motivation: Betrachtung des Bruchs |
38304
————— 2464 |
Die Aufgabe ist jetzt den Bruch zu kürzen. Dazu darf man Zähler und Nenner durch den größten gemeinsamen Teiler von a:=38304 und b:=2464 dividieren. Nur wie findet man den ggT(38304, 2464) praktisch?
Der ggT existiert immer.
Dies wurde bereits beim Teilen mit Rest und den Sätzen der Teilbarkeit
erläutert.
Wenn d der ggT(38304, 2464) ist, dann gilt sicher d|a und d|b. Damit gilt auch
d|(a-b) und d|(a-2·b), d|(a-3·b), d|(a-4·b), ....
In den Klammern stehen die Reste beim Dividieren mit Rest.
Beim Teilen von a durch b mit Rest erhält man also entweder den Rest 0,
womit in b der ggT gefunden wäre oder den Rest r, der wieder durch d teilbar
ist. Die Zahlen b und r nimmt man als Ausgangspunkt für den nächsten
Schritt und teilt b durch r mit Rest, usw..
Im Beispiel sieht das wie folgt aus:
38304 = 15·2464 + 1344
Der Rest ist nicht 0 Þ d|1344 und d|2464 und der Algorithmus kann fortgesetzt werden:
2464 = 1·1344 + 1120
1344 = 1·1120 + 224
1120 = 5·224 + 0
224 ist der erste Teiler, der den Rest 0 liefert Þ 224 = ggT(38304,2464).
| Dieses Verfahren wurde erstmals von Euklid in seinem Werk "Die Elemente" beschrieben und ihm zu Ehren Euklidischer Algorithmus genannt. |  |
Beispiele:
| a =
15642 b = 3476 |
a = 4·3476 + 1738 3476 = 2·1738 + 0 |
Þ ggT(15642, 3476) = 1738 |
| a =
1212121 b = 4545 |
a = 266·4545 + 3151 4545 = 1·3151 + 1394 3151 = 2·1394 + 363 1394 = 3·363 + 305 363 = 1·305 + 58 305 = 5·58 + 15 58 = 3·15 + 13 15 = 1·13 + 2 13 = 6·2 + 1 2 = 2·1 + 0 |
Þ ggT(1212121,4545) = 1 |
| a =
987654 b = 6542 |
a = 150·6542 + 6354 6542 = 1·6354 + 188 6354 = 33·188 + 150 188 = 1·150 + 38 150 = 3·38 + 36 38 = 1·36 + 2 36 = 18·2 + 0 |
Þ ggT(987654,6542) = 2 |
Lemma von Bachet
Aus dem Euklidischen ergebt
sich noch eine weitere wichtige Aussage. Löst man den euklidischen Algorithmus
rückwärts auf, so erhält man immer eine Darstellung des ggT(a,b)
als Linearkombination von a und b,
d.h. es existieren k,l
Z
mit:
ggT(a,b) = k·a + l·b.
Der sogenannte Berlekamp-Algorithmus liefert parallel zum ggT (durch den Eukidischen Algorithmus) auch die Darstellung des ggT.
Beispiele:
a = 144, b = 19
|
(I)
|
144
|
= |
1
|
·144 |
+
|
0
|
·19 | |
|
(II)
|
19
|
= |
0
|
·144 |
+
|
1
|
·19 | |
|
(III)
|
11
|
= |
1
|
·144 |
-
|
7
|
·19 |
(I)-7·(II)
|
|
(IV)
|
8
|
= |
-1
|
·144 |
+
|
8
|
·19 |
(II)-(III)
|
|
(V)
|
3
|
= |
2
|
·144 |
-
|
15
|
·19 |
(III)-(IV)
|
|
(VI)
|
2
|
= |
-5
|
·144 |
+
|
38
|
·19 |
(IV
)-2·(V)
|
|
(VII)
|
1
|
= |
7
|
·144 |
-
|
53
|
·19 |
(V)-(VI)
|
a = 987654, b = 6542
|
(I)
|
987654
|
= |
1
|
·987654 |
+
|
0
|
·6542 | |
|
(II)
|
6542
|
= |
0
|
·987654 |
+
|
1
|
·6542 | |
|
(III)
|
6354
|
= |
1
|
·987654 |
-
|
150
|
·6542 |
(I)-150·(II)
|
|
(IV)
|
188
|
= |
-1
|
·987654 |
+
|
151
|
·6542 |
(II)-(III)
|
|
(V)
|
150
|
= |
34
|
·987654 |
-
|
5133
|
·6542 |
(III)-33·(IV)
|
|
(VI)
|
38
|
= |
-35
|
·987654 |
+
|
5284
|
·6542 |
(IV
)-(V)
|
|
(VII)
|
36
|
= |
139
|
·987654 |
-
|
20985
|
·6542 |
(V)-3·(VI)
|
|
(VIII)
|
2
|
= |
-174
|
·987654 |
+
|
26269
|
·6542 |
(VI)-(VII)
|
Übungen:
Herr Karstens möchte 80-Pf-Marken in 60-Pf-Marken umtauschen. Für welchen Betrag muss er mindestens umtauschen? Löse die entsprechende Aufgabe für 50-Pf-Marken, die in 15-Pf-Marken umgetauscht werden sollen.
Ein rechteckiges, 270m langes und 252m breites Grundstück soll in lauter gleich große quadratische Gärten aufgeteilt werden. Gib mehrere Möglichkeiten an. Welche Lösung kommt noch in Frage, wenn die Gärten so groß wie möglich sein sollen?