Prove that $\gcd(a,b) = \gcd(b, r) \neq \gcd(a, r)$ where $r$ is the remainder of dividing $a$ by $b$

Question

I can't found an explanation on why $\gcd(a,b) \neq \gcd(a, r)$, where $r$ is the remainder of dividing $b$ by $a$

I set $r = a - bq$, so if $d \mid a$ and $d \mid b$ then $d \mid r$.

If now I set $bq = a - r$, if $d \mid a$ and $d \mid r$, then $d \mid b$.

So I can deduce that $\gcd(a, b) = \gcd(a, r)$, however this is not true.

Is that because in the first case I found $s, t$ such that $as + bt = r$, where in the second case I found $s, t, z$ such that $as + rt = bz$?

Answer 1

In the second case you can only conclude that $d|bq$. In fact if $d|a$ and $d|b$ then $d|b$ and $d|r$ since $r=a-bq$. Reciprocally, if $d|b$ and $d|r$, then $d|a$ because $a=bq+r$ and $d|r$. It follows that the common divisors of $a$ and $b$, and the common divisors of $b$ and $r$ are exactly the same hence their maximal element are the same : $\gcd(a,b)=\gcd(b,r)$.

Answer 2

$(a,r) = (a,a\!-\!qb) = (a,qb).\, $ But $\,(a,qb) = (a,b) =:d\! \iff (a/d,q) = 1\ $ since

$$\qquad\ \ \ (a,qb) = d(a/d,qb/d) = d(a/d,q)\ $$

So it fails precisely when $\,q\,$ has a prime factor $\,p\,$ that divides $\,a/d = a/(a,b),\,$ i.e when $\,p\,$ occurs to higher power in $\,a\,$ than in $\,b,\,$ so we get at least one more factor of $\,p\,$ from $\,a$ & $q\,$ in $(a,qb)$ vs. $(a,b)$.