# Division Algorithm

For any integer $a$ and positive integer $b$, there exist unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < b$.

## Proof

Existence: Let $S=\{a-nb\mid n\in \mathbb{Z}\}.$ The intersection of the sets $S$ and $\mathbb{N}$ is non-empty and has a positive element (take $n=-|a|$). By the Well Ordering Principle , it contains a least element. Let $r$ equal the value of the least element and let $q$ equal the respective value of $n$. Therefore, $r=a-qb\Rightarrow a=qb+r$. Now we prove that $0\leq r by contradiction. Let $r\geq b$. Then $r=a-qb\Rightarrow r-b=a-(q+1)b$. However, this leads to a contradiction ($r$ is supposed to be the smallest positive value that can be expressed in the form $a-nb$, but $r-b$ is smaller, positive, and can also be expressed in this manner). Therefore, $0\leq r.

Uniqueness: Let $a=qb+r=q'b+r'$. Then $qb+r=q'b+r'\Rightarrow (r-r')=b(q'-q)$. Then $|r-r'|$ is a multiple of $b$. However, since $0\leq r and $0\leq r, then $0\leq |r-r'|. The only multiple of $b$ that $|r-r'|$ can equal is $0$. Therefore, $|r-r'|=0\Rightarrow r=r'$. Since $b\not= 0$, $|q'-q|=0\Rightarrow q=q'$.

## Divisibility

If $a=qb+r$ and $r=0$, then we say $b\mid a$ or "$b$ divides $a$". Note that every integer divides $0$.