ggT-Beweis - Bestehenbleiben nach Subtraktion

Question

Wie kann man zeigen, dass der ggT von a und b der ggT von a-qb und b ist mit q aus den ganzen Zahlen? Der Beweis scheint nicht schwer zu sein, aber mir ist er einfach nicht klar.

Answer 1

es genügt zu zeigen, dass \( ggT(a, b) = ggT(a - b, b) \).

Sei \( d = ggT(a, b) \), sodass \( a = da^* \) und \( b = db^* \). Dann gilt \( a - b = d(a^* - b^*) \) mit teilerfremden \( a^*\) und \( b^* \).

Es gilt nun \( ggT(a-b, b) = ggT(d(a^* - b^*), db^*) = d \cdot ggT(a^* - b^*, b^*) \).

Nun ist zu zeigen, dass \( ggT(a^* - b^*, b^*) = 1 \) gilt, was stimmt, da \( d \) als ggT maximal gewählt war. Zu dieser Maximalitätsforderung stünde im Widerspruch, dass \( ggT(a^* - b^*, b^*) = d^* > 1 \) gilt.

MfG

Mister