Question

Bestimmen Sie ggT(144, 196) und finden Sie ganze Zahlen a, b mit der Eigenschaft, dass 144a +
196b = ggT(144, 196). Sind diese Zahlen eindeutig?

Der ggT(144, 196)= 4

Meine Frage lautet, wie kriege ich die ganzen Zahlen rechnerisch für a und b heraus?

Comments

Nutze den erweiterterten euklidischen Algorithmus

---

Vom Duplikat:

Titel: Bestimmen Sie ggt(144, 196)

Stichworte: ggt

Bestimmen Sie ggT (144,196) und finden Sie ganze Zahlen $a, b$ mit der Eigenschaft, dass $144 a+$ $196 b=\operatorname{gg} \mathrm{T}(144,196) .$ sind diese Zahlen eindeutig?

Answer 1

196·x + 144·y = ggt(196, 144)

Euklidischer Algorithmus
196 = 1·144 + 52
144 = 2·52 + 40
52 = 1·40 + 12
40 = 3·12 + 4 --> 4 = 40 - 3·12 → 4 ist der ggT und der beginn des nächsten Algorithmus
12 = 3·4 + 0

Erweiterter Euklidischer Algorithmus
4 = 40 - 3·12
4 = 40 - 3·(52 - 1·40) = -3·52 + 4·40
4 = -3·52 + 4·(144 - 2·52) = 4·144 - 11·52
4 = 4·144 - 11·(196 - 1·144) = -11·196 + 15·144

Answer 2

144a+196b=4

(36a+49b)*4=4

36a+49b=1

Wir suchen ein Vielfaches von 36, das beim Dividieren durch 49 den Rest 1 hat.

	36	72	108	-->·5	540
Rest	36	23	10	-->·5=50	1

540=15·36

539=11·49

15·36+(-11)·49=1

15·144+(-11)·196=4=ggT(144;196)

Allgemein: a=-49n-34   ;   b=36n+25

Answer 3

Aloha :)

Der Euklidische Algorithmus nutzt aus, dass $\operatorname{ggT}(a,b)=\operatorname{ggT}(a-b,b)$ ist:

$$\operatorname{ggT}(144,196)=\operatorname{ggT}(144,52)=\operatorname{ggT}(92,52)=\operatorname{ggT}(40,52)=\operatorname{ggT}(40,12)$$$$=\operatorname{ggT}(28,12)=\operatorname{ggT}(16,12)=\operatorname{ggT}(4,12)=\operatorname{ggT}(4,8)=\operatorname{ggT}(4,4)=4$$

Das kann man natürlich auch schneller machen, indem man direkt mehrfach den kleineren Wert subtrahiert:

$$\operatorname{ggT}(144,196)=\operatorname{ggT}(144,52)=\operatorname{ggT}(40,52)=\operatorname{ggT}(40,12)=\operatorname{ggT}(16,12)$$$$=\operatorname{ggT}(4,12)=\operatorname{ggT}(4,4)=4$$