对任意整数a，b，b>0，存在唯一的整数q，r，使a=bq+r，其中0≤r<b，这个事实称为带余除法定理，是整除理论的基础。若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，且d可被a，b的任意公因数整除则称d是a，b的最大公因数。当d≥0时，d是a，b公因数中最大者。若a，b的最大公因数等于1，则称a，b互素。累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。

带余除法的证明：【存在性】作整数序列

…，-3b，-2b，-b，0，b，2b，3b，…

则a必在上述序列的某两项之间，即存在一个整数q使得

qb≤a<(q+1)b

成立。令a-qb=r,即证存在性。

【唯一性】设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,这是不可能的。即证唯一性。