prove by induction; integer division by $5$

Question

I'm having trouble with my math project. I have to prove that for very natural, $n$, there is an integer $q$ , and an integer $r$ such that: $n=5q+r$ and $0\le r<5$ using induction

I have tried using the axiom of Archimedes but I can't really get around the problem. Sorry if this seems basic , I still have a really hard time with demonstrations

Answer 1

Hint

Suppose it is true for a certain $n\geq 0.$

then

$$n+1=5q+r+1$$ with $0\leq r<5$.

• If $r=4$ then

$$n+1=5(q+1)+0$$

• If $0\leq r\leq 3$ then

  $0\leq r+1<5$ and $n+1=5q+(r+1)$.

Answer 2

Start with the base case: $n=0$. Then, clearly $n=5\cdot 0+0$, so we are okay.

Next, suppose that the result holds for some fixed integer $n\geq 0$. We want to prove that the result holds for $n+1$. I.e., we want to prove that there exist integers $q$ and $0\leq r< 5$ satisfying $n+1=5q+r$.

By the inductive hypothesis, there are integers $q'$ and $0\leq r'<5$ such that $n=5q'+r'$. But this means that $n+1=5q'+r'+1$. Are we finished? If $r'+1<5$, then yes (take $1=1'$ and $r=r'+1$). But what if $r'+1=5$. This happens precisely when $r'=4$. Then you have $n+1=5q'+5$. Do you see what you can do here?

Answer 3

For variety we prove it by strong iduction: $ $ if $\,n<5\,$ then $\ n = 0\cdot q+ n.\ $ Else $n\ge 5\,$ hence by strong induction $\, 0\le n\!-\!5 = 5q+r\,\ $ so $\ \,n = 5(q\!+\!1)+r. $