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 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!
 A: You're overthinking, in my opinion.
Do induction on $a$.
For $a=0$, the statement is true: $0=b0+0$ and $0<b$.
Suppose $a>0$ and that the statement holds for all $c<a$.
If $a<b$, then $a=b0+a$ and $a<b$. If $a\ge b$, then $a-b<a$, so $a-b=bq+r$ with $r<b$; since $a=b(q+1)+r$, we're done.
A: 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'<a$ can be written as $qb+r$, with $r<b$. Now, if $a<b$, 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<b$. But then $a=(q+1)b+r$.
A: 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$. 
