0

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.

Matthew Leingang
  • 26,112
Christian Soto
  • 1

2 Answers2

1

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?

Matthew Leingang
  • 26,112
1

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

Doug M
  • 57,877