1. ## Proving division algorithm

Hi all,

I'm having a tough time trying to go through the division algorithm proof.

Theorem: Let (a,b) be two integers. Then there exists numbers q and r with a>= 0, 0=<r<=b such that a=bq+r.

In class, my professor starts the proof by using cases, but I don't really understand why he does this.

Case 1- If b>a then a=o*b+ a (0<a<b) q=0, r=a
Case 2- if b=a then a=b*1+0, q=1, r=0
Case 3- if b<a then a*1 ( I think my notes get cut off here since I was pretty confused in class).
Does anyone know where he is trying to go with this? Thanks

2. Originally Posted by jusstjoe
Hi all,

I'm having a tough time trying to go through the division algorithm proof.

Theorem: Let (a,b) be two integers. Then there exists numbers q and r with a>= 0, 0=<r<=b such that a=bq+r.

In class, my professor starts the proof by using cases, but I don't really understand why he does this.

Case 1- If b>a then a=o*b+ a (0<a<b) q=0, r=a
Case 2- if b=a then a=b*1+0, q=1, r=0
Case 3- if b<a then a*1 ( I think my notes get cut off here since I was pretty confused in class).
Does anyone know where he is trying to go with this? Thanks
Hi jusstjoe.

The result won’t work if $\displaystyle b=0.$ However I gather from your post that you want $\displaystyle a$ and $\displaystyle b$ to be both positive integers.

Start by showing that the set $\displaystyle \{n\in\mathbb N:nb\ge a\}$ is not empty. This will be true in Cases 1 and 2 with $\displaystyle n=1.$ For Case 3, suppose to the contrary that $\displaystyle nb<a$ for all natural numbers $\displaystyle n.$ Then, in particular, $\displaystyle ab<a$ $\displaystyle \implies$ $\displaystyle b<1$ which is not possible if $\displaystyle b$ is a positive integer. Hence there is a natural number $\displaystyle n$ such that $\displaystyle nb\ge a.$ Let $\displaystyle q_0$ be the smallest such natural number. The proof is completed by taking $\displaystyle q=q_0-1$ and $\displaystyle r=a-bq-1.$