# Prove or disprove $\gcd(q,r) \mid b$ if $a = bq + r$

Prove or disprove $\gcd(q,r) \mid b$ if $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$

I'm pretty sure it's true (I can't think of a counter example), but I don't see how to prove it.

Some of my approaches:

$d = \gcd(q,r)$

$d = \gcd(q, a-bq)$

Clearly $d\mid q$ and $d\mid r$ and $d\mid(a-bq)$, but I don't see any way to conclude that $d\mid b$, and approaching it from the other side with $b = \frac{a-r}{q}$ is no help either.

• In the hypothesis the equality $a=bq+r$ is just chaff because the thesis has nothing to do with $a$. To find a counter example just pick $q,r$ and $b$ such that $\gcd(q,r)$ does not divide $b$. – Git Gud Oct 27 '14 at 20:53
• Perhaps the question is supposed to be asking about $\gcd(a, r) \mid b$. That makes a bit more sense. – apnorton Oct 27 '14 at 20:58
• I forgot part of the question: $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$ – Zout Oct 27 '14 at 21:01

As said in the comments, it is false as stated. The statement $\gcd(q,r)\mid b$ has nothing to do with $a$, so we are free to choose $b,q$ and $r$.
We can take for example $b=1$ and $q=r=2$. Or if you want $0\leqslant r<q$, let $b=1$, $q=4$, $r=2$.