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<b$ 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<b$ .

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<b$ and $0\leq r<b$ , then $0\leq |r-r'|<b$ . 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'$ .