ggT(m,n) = sm + tn Beweis

Lassen$g = \gcd(m, n)$. Note that $g \mid m$ and $g \mid n$, so $g \leq m$ and $g \leq n$.

Suppose that $s, t > 0$. Then $t \geq 1$. But this is absurd, since it follows that:

$$g = sm + tn > 0m + tn = tn \geq 1n = n$$ so dass $g > n$, im Widerspruch zu der Tatsache, dass $g \leq n$.

---

Sie haben Recht für den Fall, wo$s,t < 0$. Das impliziert es$-g$ein größerer gemeinsamer Teiler von ist$a$Und$b$als$g$, ein Widerspruch.

Brechen Sie es in einen Fall auf, in dem$gcd(m,n) = 1$und ein Fall, wo$gcd(m,n) > 1$.

Für den ersten Fall sollte klar sein, dass s und t nicht beide positiv/negativ sein können. Lassen Sie mich wissen, wenn Sie weitere Erklärungen dazu benötigen.

Nehmen Sie für den zweiten Fall (zum Widerspruch) an, dass s und t beide positiv sind. Seit$gcd(m,n) = d > 1$, gibt es ganze Zahlen p, q so dass$m=dp$Und$n=dq$. Und da s und t beide positiv sind,$gcd(m,n) = sm + tn = sdp + tdq$. Dies ist jedoch größer als d, da t und s beide positiv sind.