首先先说一下整除的概念

整除：设a , b是两个整数，且b！=0 .如果存在整数 c ,使得 a = b * c,则称a被b整除，或 b 整除 a ，记做 b|a 

           此时，又称 a 是 b 的倍数, b 是 a 的因子。



接下来就是带余除法的定义及其证明:

带余除法：设a , b是两个整数,且b != 0,则存在唯一的整数 q , r (0 <= r < |b|),使得

                  a = q * b + r , (0 <= r < |b|)


证明带余除法：

—————————————————————————————————————————————

1. 我们首先要证明 0<= r <b:

    设集合 S 是a - b * k 组成的所有整数，其中 k 为整数，即s={a - b * k | k ∈ Z} .设T是S中所有非负整数组成

    得集合。

    则T是非空的（因为当k等于由（小于a / b的集合中）的整数时，b * k < a, 所以此时a - b * k>0,所以T非

    空）。所以易得T中得最小元素 r = a - b * q(此处的r , q与带余除法中得意义一样)。且r >= 0(因为T是非

    负集合) 且r < b(我们可以用反证法来证明 r < b,如果r >= b ,则  r > r - b >= 0,则r - b=a - b * (q+1) 

    >= 0,所以此时r-b是T中得最小元素，这一推论与r是T中最小元素相悖）

    所以 a = b * q + r, ( 0 <= r < b);

2 .接下来我们要证明q 和 r 是惟一的:

    我们假定有两个方程  a = b * q1 +r1和 a = b * q2 + r2,(0 <= r1< b,0 <= r2 < b);两式相减得

                                          r2 - r1 =b * (q1 - q2)

    其中q != 0,所以 b 整除r2 - r1，即 b|( r2- r1)。

   又0 <= r1< b,0<= r2<b，所以-b < r2- r1 < b.所以结合 b|( r2 - r1), r2 - r1只能等于0，所以r2== r1.

   又因为b * q1+ r1 == b * q2 + r2,所以q2==q1;

   所以 q 和 r 是惟一的。


以上我们可以得到对于两个整数a,b,当b!=0时，存在惟一的整数q , r(0 <= r <b),使得

a=q * b +r (0 <= r <b);


证毕

—————————————————————————————————————————————