GCD(m,n) = sm + tn proof

Question

Suppose that m and n are positive integers and that s and t are integers such that gcd(m,n) = sm + tn. Show that s and t cannot both be positive or both be negative. I understand that if both of them are 1, then the GCD of m and n is equal to m and n and that can't be true. Also, if both of them are negative, then the GCD of two positive integers would be negative. This also cannot be true. However, is there a way to prove this?

Answer 1

Let $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 that $g > n$, contradicting the fact that $g \leq n$.

---

You are correct for the case where $s,t < 0$. It implies that $-g$ is a larger common divisor of $a$ and $b$ than $g$, a contradiction.

Answer 2

Break it into a case where $gcd(m,n) = 1$ and a case where $gcd(m,n) > 1$.

For the first case, it should be clear that s and t cannot both be positive/negative. Let me know if you need more explanation on that.

For the second case assume (for contradiction) that s and t are both positive. Since $gcd(m,n) = d > 1$, there exists integers p, q such that $m=dp$ and $n=dq$. And since s and t are both positive, $gcd(m,n) = sm + tn = sdp + tdq$. But this is greater than d since t and s are both positive.