带余数除法dai yushu chufa
也叫带余除法.若a,b是两个整数，其中b>0，则存在两个整数q和r，使得等式
a=bq+r,0≤r成立，而且q及r是唯一的.
这个定理的证明如下：考察整数序列…，-3b,-2b,-b,0,b,2b,3b，…，则整数a必在这个序列的某相邻二项之间，即存在一个整数q，使得qb≤a<(q+1) b成立.令a-qb=r，即得a=bq+r，且0≤r1,r1，是满足(|)式的另一对整数.即a=bq1+r1,0≤r11+r1＝bq+r，于是b (q-q1)=r1-r.进一步有b|q-q1|=|r1-r|.由于r及r1都是小于b的非负整数，所以上式右边是小于b的，如果q≠q1，则上式左边≥b，这不可能.由此可得q=q1，从而r=r1.
我们把(1)式中的q叫做a除以b所得的不完全商，r叫做a被b除所得的余数.也叫做最小非负剩余.利用带余数除法定理可以把全体整数进行分类.例如取4作为除数，可以把全体整数分成4k型，4k+1型，4k+2型及4k+3型四类.在同余理论中，剩余类及完全剩余系也是建立在这个定理的基础上的.