# prove by induction; integer division by $5$

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

• This is the division algorithm. – SchrodingersCat Dec 17 '16 at 14:32
• Do you know strong induction? (a.k.a. complete induction or course of values) – Bill Dubuque Dec 17 '16 at 14:32
• Have you tried finding a counterexample? Did you notice something? Also I agree, induction is the way to go here. But it might help you to play a little around. – SAJW Dec 17 '16 at 14:35
• Also , you can apply Well-ordering principle. – Behrouz Maleki Dec 17 '16 at 14:38

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?

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

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