Mit Hilfe des euklidischen Algorithmus ggT und kbV berechnen

Question

Aufgabe 4
Berechnen Sie mit Hilfe des euklidischen Algorithmus die folgenden Zah- len:
(a) ggT(23452,7892)
(b) kgV(234,89)
(c) ggT(612,629):
(a) ggT(23452,7892)
(b) kgV(234,89)
(c) ggT(612,629)

Answer 1

Den ggT berechnet man über die Division mit Rest. Und zwar teilt man solange die grössere durch die kleinere Zahl, bzw. durch den Divisionsrest, bis man als Rest 0 erhält. Im Aufgabe a führt 16/4 dazu, dass der Rest 0 ist. Von daher ist 4 das Ergebnis, da sich beide Zahlen dadurch teilen lassen.

a) ggT(23452,7892)

23452 / 7892 = 2 * 7892 + 7668

7892 / 7668 = 1 * 7668 + 224

7668 / 224 = 34 * 224 + 52

224 / 52 = 4 * 52 + 16

52 / 16 = 3 * 16 + 4

16 / 4 = 4 * 4 + 0

ggT= 4

b) kgV(234,89)

Das kgV lässt sich über den ggT ausrechnen. Sobald man mit dem Algorithmus von Euklid an den ggT gekommen ist, kann man folgende Formel (Wikipedia) nutzen:

ggT(m,n) · kgV(m,n) = |m·n|

ggT(234,89)
234 / 89 = 2 * 89 + 56
89 / 56 = 1 * 56 + 33
56 / 33 = 1 * 33 + 23
33 / 23 = 1 * 23 + 10
23 / 10 = 2 * 10 + 3
10 / 3 = 3 * 3 + 1
3 / 1 = 3 * 1 + 0
ggT= 1

Der ggT ist 1. Dass heisst, es gibt keinen grössten gemeinsamen Teiler, ausser dem trivialen.

Nun wendet man die Formel an:
ggt(234,89) * kgV(234,89) = |m * n|
1 * kgV(234,89) = |234 * 89|
kgV(234,89) = 20.826



c) ggT(612,629)
629 / 612 = 1 * 612 + 17
612 / 17 = 36 * 17 + 0
ggT = 17