# Divisibility Problem: How can I solve this?

Suppose that $a,b,q,r$ are any integers such that $b > 0$ and $a = bq + r$, with $0\le r<b$, and suppose $b|a$.

Must it be the case that $r = 0$? Justify your answer.

Can anyone please let me know how can I start this problem ? Thanks

• Given that $b\mid a$, consider $a-bq$. May 19, 2014 at 7:39

Hint: since $b|a$, this means that (by definition) $a=k\cdot b$ for some $k\in\mathbb Z$. This means that $$qb+r=kb.$$

All you have to prove now is that $q=k$.

Hint 2: The equation is equivalent to $r=(k-q)\cdot b$.

• Hey 5xum, first of all thank for your Hint. Here is what I got: solve for r = a-bq and then replace r in qb+r=kb which we get qb+a-bq=kb. Then replace kb for a and we get qb+kb-bq=kb.>> qb-bq=kb-kb>>cancel out b we get q-q=k-k>>0=0. Therefore, q=k and we can conclude that r=0. What do you think? May 19, 2014 at 7:55
• Totaly false. You say that from $q-q=k-k$, it follows that $q=k$. Does that mean that, since $2-2=10-10$, that $2=10$?
– 5xum
May 19, 2014 at 7:56
• thank for the 2nd hint. So at this point can I set (k-q).b=0 and work it out to get k=q? May 19, 2014 at 8:14
• You cannot set $(k-q)\cdot b=0$, since that is exactly what you want to prove (i.e. that $r=0$).
– 5xum
May 19, 2014 at 8:18

To elaborate on my comment, since both $a$ (by hypothesis) and $bq$ (obviously) are multiples of $b$, $r = a-bq$ is also a multiple of $b$. How many multiples of $b$ are there in $\{0,\dots,b-1\}$?

• n time I guess ? May 19, 2014 at 8:28
• How many multiples of $3$ are there in $\{0,1,2\}$? May 19, 2014 at 8:29
• 1 because 3*0=0 May 19, 2014 at 8:32
• Yes. So, given that $r$ is a multiple of $b$ which is in $\{0,\dots,b-1\}$, it must be $0$, there are no other possibilities. May 19, 2014 at 8:33
• ok that make sense to me now. Thank a lot for your explanation. May 19, 2014 at 8:39