0 Daumen
867 Aufrufe

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?

Avatar von

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?

3 Antworten

0 Daumen

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

Avatar von 487 k 🚀
0 Daumen

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.


3672108-->·5540



Rest362310-->·5=501



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

Avatar von 47 k
0 Daumen

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$$

Avatar von 152 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community