(Division algorithm) 令 $a$ 和 $d$ 为整数且 $d \geq 1$.则存在唯一的整数 $q$ 与 $r$ 使得 $$a=dq+r$$ 且$$0\leq r\leq d-1$$

Proof:根据定理16可知，当$a$是自然数时，存在性已经得证.当$a$是负整数时，我们知道

$$-a=dq+r,0\leq r\leq d-1$$

所以当$r>0$时，

$$a=d(-q-1)+(d-r)$$

当$r=0$时，很容易.

 

这样子，存在性就证完了.下面证明唯一性:

若存在$q',r'$，使得

$$a=dq'+r'$$则$$d(q-q')+(r-r')=0$$则$d|(r-r')$,这只能推出$r=r'$(为什么?).因此$r=r'$,$q=q'$.