6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$ – Git Gud Oct 27 '14 at 20:53
  • 1
    $\begingroup$ Perhaps the question is supposed to be asking about $\gcd(a, r) \mid b$. That makes a bit more sense. $\endgroup$ – apnorton Oct 27 '14 at 20:58
  • $\begingroup$ I forgot part of the question: $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$ $\endgroup$ – Zout Oct 27 '14 at 21:01
1
$\begingroup$

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$.
Can you give another counterexample?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.