3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is the division algorithm. $\endgroup$ – SchrodingersCat Dec 17 '16 at 14:32
  • $\begingroup$ Do you know strong induction? (a.k.a. complete induction or course of values) $\endgroup$ – Bill Dubuque Dec 17 '16 at 14:32
  • $\begingroup$ 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. $\endgroup$ – SAJW Dec 17 '16 at 14:35
  • $\begingroup$ Also , you can apply Well-ordering principle. $\endgroup$ – Behrouz Maleki Dec 17 '16 at 14:38
2
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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.