带余除法的带余除法的证明

带余除法的带余除法的证明

【存在性】
给定整数,其中.设集合.
记（是自然数集）.
若,则可取小于等于的整数使得;若,则可取大于等于的整数使得.
故.由自然数集的良序性,知中有一最小元素.
设.则.
现假设.
则.故（时取加号,时取减号）
而由,则
这违反了是最小元素这一事实,於是.令,即证存在性.
【唯一性】设是满足的另一对整数，因为
，
于是

故

由于r及r1都是小于b的非负整数，所以上式右边是小于|b|的。
如果q≠q1，则上式左边≥|b|，这是不可能的。所以q=q1， r=r1，即证唯一性。