Division Algorithm Theorem

Theorem: For all $a,b\in\mathbb{Z},$ with $b>0,$ there exists unique $q,r\in\mathbb{Z}$ such that $a=bq+r$ with $0\le r<b$

Proof: Basically, $q$ is the quotient and $r$ is the remainder. Consider the set $S={a-bx|x\in\mathbb{Z},a-bx\ge0}$. For this set, we will first choose $a, b$ and vary $x$ to get elements of the set.

In general, to find the smallest element $r$ in $S$, we have to argue that the set $S$ is not empty.

Claim: $S\neq\phi$
Case 1: $a\ge0$, we set $x=0$, so that we get $a-b(0)=a\in S$. The set is not empty
Case 2: $a<0$, we will set $x=a$, so that $a-ba=a(1-b)\ge0$. The set is not empty

Let $r$ be the minimum value of $S$ and $q$ be the corresponding quotient for this value of $r$.

We have $r=a-bq$. Towards the contradiction, assume that $r\ge b$
$$r=a-bq\ge b$$ $$r-b=a-b(q+1)\ge b-b\ge0$$

This means that $r-b\in S$ because $r-b=a-b(q')$ where $q'=q+1$. But on the other hand, $r-b<r$ which contradicts our assumption that $r$ is the minimum value of $S$. This implies that $0\le r<b$

Now, all that is left is to prove the uniqueness of $q$ and $r$. Suppose that $q,q',r,r'$ are such that $a=bq+r=bq'+r'$. Assume $r'\ge r$, this assumption can work either ways. We have $b(q-q')=r'-r$. The LHS is a multiple of $b$ and the RHS follows the inequality $o\le r'-r<b$. The only way both can be true is if LHS $=$ RHS $=0$. This implies that $q=q'$ and $r=r'$. $\blacksquare$