2
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Given that $b\mid a$, consider $a-bq$. $\endgroup$
    – fkraiem
    May 19, 2014 at 7:39

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ May 19, 2014 at 7:55
  • 1
    $\begingroup$ 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$? $\endgroup$
    – 5xum
    May 19, 2014 at 7:56
  • $\begingroup$ thank for the 2nd hint. So at this point can I set (k-q).b=0 and work it out to get k=q? $\endgroup$ May 19, 2014 at 8:14
  • 1
    $\begingroup$ You cannot set $(k-q)\cdot b=0$, since that is exactly what you want to prove (i.e. that $r=0$). $\endgroup$
    – 5xum
    May 19, 2014 at 8:18
1
$\begingroup$

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\}$?

$\endgroup$
7
  • $\begingroup$ n time I guess ? $\endgroup$ May 19, 2014 at 8:28
  • $\begingroup$ How many multiples of $3$ are there in $\{0,1,2\}$? $\endgroup$
    – fkraiem
    May 19, 2014 at 8:29
  • $\begingroup$ 1 because 3*0=0 $\endgroup$ May 19, 2014 at 8:32
  • $\begingroup$ 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. $\endgroup$
    – fkraiem
    May 19, 2014 at 8:33
  • $\begingroup$ ok that make sense to me now. Thank a lot for your explanation. $\endgroup$ May 19, 2014 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .