So I am trying to Prove the division algorithm by induction. The Division Algorithm is written in my book as this:

The Divison Algorithm for Natural Numbers If $n$, $m$ are natural numbers and $n\leq m$, then either

  1. There is a natural number $q$ such that $m=nq$, or

  2. There are natural numbers $q$ and $r$ such that $m = nq+r$.

This is what I have so far,

Assume $n$ and $m$ are natural numbers and $n<m$ or $n=m$.

I have no idea how to use induction to prove this theorem. I just need help getting started.

  • $\begingroup$ Why do you want to prove it by induction? $\endgroup$ – Matthew Leingang Sep 9 '16 at 17:10

A first step to proving this by induction is to get the statement in the form $P(m)$; that is, a statement depending on a single natural number variable $m$. In this case, you can say, “Let $P(m)$ be the statement that for all natural numbers $n$ with $n \leq m$, then either ... or ... is true.”

You need to verify that $P(1)$ is true. But if $m=1$ and $n\leq m$, then $n=1$. So option 1 holds with $q=1$.

Next, you need to assume that $P(m)$ is true and show that $P(m+1)$ is true. This is going to require some case work. But consider that if $n \leq m+1$, then either $n \leq m$ or $n=m+1$.

Can you keep it going?


To apply the division algorithm $(m,n)$ with $m,n \in \mathbb N, m \le n$ we are saying that there exist $q \in \mathbb N$ and $r\in \mathbb N_0$ such that $n = mq + r, r<m, q\le n$

Show that it is true in the base case. if, $m,n=1 \implies q = 1, r = 0$

Assume that the proposition is true for some $m,n$ as described above.

We must show that $(m,n+1)$

$n+1 = mq + (r + 1)$ if $r<m-1$ and, or $n+1 = m(q+1)$ if $r = m-1.$

$(m,n) \implies (m,N>n)$

Now the normal thing to do would be to show that $(m,n) \implies (m+1,n)$ But I was running into difficulties.

How about we come from the other direction.

$(1,n)$ with $m=n \implies q=n,r=0$

$(m,n)$ with $m=n \implies q=1,r=0$

$(m-1,n)$ assuming $(m,n), m>2$

$n=qm + r\\ n=q(m-1) +q + r\\ n-q=q(m-1) + r$

If $r=m-1, n-q=(q+1)(m-1)$ otherwise $r<(m-1), (m-1, n-q)$

We have already shown that $(m-1, n-q)\implies (m-1, n)$


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.