# Proving the division theorem with strong induction

The exercise goes like this:

Prove the division theorem using strong induction. That is, prove that for $$a \in \mathbb{N}$$, $$b \in \mathbb{Z}^+$$ there always exists $$q, r \in \mathbb{N}$$ such that $$a = qb + r$$ and $$r < b$$. In particular, give a proof that does not use $$P(n−1)$$ to prove $$P(n)$$ when $$b > 1$$.

I have done a few proofs with strong induction before, but never with a predicate with multiple variables, so I'm unsure how to approach this.

One idea I had, was to write use the following as my predicate:

$$P(a,b):= \exists r,q\in\mathbb{N}(a=b\cdot q+r)$$

and then use $$\forall b \in \mathbb{Z}^+ .\forall i < a(P(i, b))$$ as my first inductive hypothesis, and $$\forall a \in \mathbb{N} .\forall i < b(P(a, i))$$ as my second, proving them separately. But I'm not sure this is right, as I can't seem to prove it this way.

Am I even on the right track here? Any help would be much appreciated!

You're overthinking, in my opinion.

Do induction on $$a$$.

For $$a=0$$, the statement is true: $$0=b0+0$$ and $$0.

Suppose $$a>0$$ and that the statement holds for all $$c.

If $$a, then $$a=b0+a$$ and $$a. If $$a\ge b$$, then $$a-b, so $$a-b=bq+r$$ with $$r; since $$a=b(q+1)+r$$, we're done.

The idea is that the set $$S$$ of integers of the form $$\, a - n b\,$$ is closed under subtraction by $$b$$ so we can continually subtract $$b$$ from $$a$$ till we reach an element $$< b.\,$$ Indeed, apply the following.

Lemma $$\$$ If nonempty $$S\subseteq \Bbb N\,$$ is closed under subtraction $$\!\ge 0\,$$ by $$\,b,\,$$ i.e. $$\,s\ge b\in S\Rightarrow\, s-b \in S\,$$ then $$S$$ contains a natural $$< b$$

Proof $$\$$ The least $$\,\ell\in S$$ must satisfy $$\,\ell < b,\,$$ else $$\,\ell-b\in S$$ would be a smaller element of $$S$$.

You can prove it by strong induction on $$a$$.

For $$a=0$$, it is trivial.

Now, consider an arbitrary $$a\in\mathbb N$$ and assume that each $$a' can be written as $$qb+r$$, with $$r. Now, if $$a, you can write $$a$$ as $$0\times b+a$$. Otherwise, consider $$a-b$$. By the induction hypothesis, it can be written as $$bq+r$$, with $$r. But then $$a=(q+1)b+r$$.