Division Algorithm proof

Question

May someone tell me if there is anything wrong with my proof? And what can I do to improve it, please?

So the theorem is

Let a,b$\in$ $\mathbb{N}$ with b$>$0. Then $\exists$ q,r$\in$ $\mathbb{N}$ : $a=qb+r$ where $0 \leq r < b$

Now, I'm only considering the case where $b<a$.

Proof: Let $a,b\in\mathbb{N}$ such that $a>b$. Assume that for $1,2,3,\dots,a-1$, the result holds. Now consider three cases: 1) a-b=b and so setting q=1 and r=0 gives the desired result. 2) a-b$<$b and so setting q=0 and r=a-b gives the desired result. 3)$a-b>b$ and since a-b$\geq$ 1 it follows by the induction hypothesis that there exists t and r such that a-b=bt+r and so setting q=t+1 gives the desired result.

Answer 1

The strong induction hypothesis is

For every $a'$, with $b<a'<a$, there exist $t$ and $r$ such that $a'=bt+r$, with $0\le r<b$.

You have $a-b<a$, but you don't know whether $a-b>b$. However the case $a-b\le b$ is easily taken care of: in case $a-b<b$ you can set $t=0$ and $r=a-b$; in case $a-b=b$ then take $t=1$ and $r=0$. If $a-b>b$, then the strong induction hypothesis provides $t$ and $r$ with $a-b=bt+r$ and $0\le r<b$. Then you can set $q=t+1$.

On the other hand, you can simply avoid the assumption that $a>b$. The strong induction hypothesis then can be

For every $a'<a$, there exist $q$ and $r$ such that $a'=bt+r$, with $a'=bt+r$ and $0\le r<b$.

If $a\le b$, you can do as done before. If $a>b$, then $a-b<a$ and you can use the induction hypothesis.

Answer 2

This doesn't answer your questions about the proof you gave, but you might want to note that there's a different approach that doesn't use induction explcitly - it seems simpler to me, or at least cleaner:

Define $$R=\{r=a-qb: q\in\Bbb N, r\ge0\}.$$Taking $q=0$ shows that $R$ is nonempty. Any nonempty set of non-negative integers has a smallest element; let $r_0$ be the smallest element of $R$.

You're done if you can show that $r_0<b$. But it's easy to show this:

If $r_0\ge b$ then $r=r_0-b\in R$.

Since $r_0-b<r_0$ this shows that if $r_0\ge b$ then $r_0$ is not the smallest element of $R$, contradiction.

Edit: I've been asked why I would ocnsider that set. Hmm...

Define $r$ to be a function of $q$; $$r(q)=a-qb.$$We need to show

There exists $q$ suuch that $0\le r(q)<b$.

How might we try to find such a $q$? Well, it's pretty clear that if we first restrict attention to $q$ such that $r(q)\ge0$, then if there does exist a $q$ with $r(q)<b$, the smallest possible $r(q)$ must work. So we choose $q$ to minimize $r(q)$ (again, subject to the restriction that $r(q)\ge0$.

And now letting $R$ be that set and taking the smallest element of $R$ is the obvious way to show formally that there is a $q$ that minimizes $r(q)$.

Note The statement that every non-empty subset of $\Bbb N$ has a smallest element says that $\Bbb N$ is "well-ordered". The fact that $\Bbb N$ is well ordered is equivalent to the validity of proof by induction - any proof by induction has an equivalent version using well-ordering and vice-versa. Sometimes one comes out seeming simpler, sometimes the other.

Comment: The tags seem to indicate you're taking a course in abstract algebra. It's going to happen a lot that proofs of things involve defining a certain set and deducing properties of it. (If $G$ is a finite group and $a\in G$ then the order of $a$ divides the order of $G$: Let $S$ be the subgroup of $G$ generated by $a$...)