解释
对任意整数a，b且b≠0，存在唯一的数对q，r，使a=bq+r，其中0≤r<|b|。这个事实称为带余除法定理，是整除理论的基础。若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，d≥0，且d可被a，b的任意公因数整除，则称d是a，b的最大公因数。若a，b的最大公因数等于1，则称a，b互素。累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。
除法证明
【存在性】
设集合S={…，a-3b，a-2b，a-b，0，a+b，a+2b，a+3b，…}={a+bk: k是整数}
记T为S和自然数集的交集，T非空，由自然数集的良序性，知T中有一最小元素t。
设t=a-bq，q为整数。则a-bq≥0。
现假设a-bq≥|b|，但这样便有a-b(q±1)≥0成立(b为正数时取加号，负数时取减号)，且a-b(q±1)≤a-bq。
这违反了t是最小元素这一事实，于是a-bq<|b|。令r=a-qb，即证存在性。
【唯一性】设q1、r1是满足a=bq+r，0≤r<|b|的另一对整数，因为
bq1+r1=bq+r，
于是
b(q-q1)=r1-r
故
|b||q-q1|=|r1-r|
由于r及r1都是小于b的非负整数，所以上式右边是小于|b|的。
如果q≠q1，则上式左边≥|b|，这是不可能的。所以q=q1， r=r1，即证唯一性。
