原文

定义1 

如果a和b为整数且a≠0，我们说a整除b是指存在整数c使得b=ac。如果a整除b，我们还称a是b的一个因子，且称b是a的倍数.

如果a整除b，则将其记为a | b，如果a不能整除b，则记其为a ∤b。

定理1

如果a，b和c是整数，且a | b，b|c，则a|c.

证明：因为a l b，b | c，故存在整数e和f，使得ae = b，bf = c。

因此c = bf = (ae)f = a(ef)，从而得到a | c

例如：因为11 | 66，66 | 198，故由定理1可知11 | 198

定理2

如果a，b，m和n为整数，且c | a，c | b，则c | (ma+nb).

证明：因为c | a且c | b，故存在整数e和f，使得a = ce，b = cf。

因此，ma + nb = mce + ncf = c(me + nf)，从而c | (ma+nb)。

例如：由于3 | 21，3 | 33，故由定理2可知3能够整除5*21 - 3*33  = 105 - 99 = 6。

定理3

带余除法 如果a和b是整数且b > 0，则存在唯一的整数q和r，使得a = bq + r,  0 ≤ r < b。

在带余除法给出的公式中，我们称q为商，r为余数，我们还称a为被除数，b为除数。

例如：如果a=133，b=21，则q=6，r=7，因为133-21*6+7且0<7<21。

类似地，如果a=-50，6=8，则q=-7，r=6，因为-50 = 8*(-7)+6且0<6<8.

我们注意到a能被b整除当且仅当在带余除法中的余数为0。

证明

（1）存在性

考虑形如a-bk所有整数集合S，其中k为整数。设T是S中的所有非负整数构成的集合，T是非空的，因为当k是满足k < a/b的整数时，a-bk是正的。

T中有最小元r = a-bq。(q和r的值如定理中所述.)

根据r的构造可知 r ≥ 0，且容易证明r < b。

如果r≥b，则r > r-b = a - bq - b = a - b(q+1) ≥ 0，这与我们选择r=a-bq为形如a-bk的整数中的最小元矛盾，因此0 ≤ r < b.

（2）唯一性

为了证明q和r的值是唯一的，我们假定有两个方程a=b*q1+r1和a=b*q2+r2，满足0 ≤ r1<b，o≤r2<b，把第二个方程从第一个方程中减去，可得0 = b(q1-q2)+(r1-r2).

因此，r2 - r1 = b(q1-q2)，由此可知b整除r2-r1。因为0≤r2<b，0≤r1<b，故-b<r2-r1<b，因此b可以整除r2-r1只有当r2 - r1=0，

或者，换句话说，当r1 = r2时，因为bq1+r1 = bq2+r2，且r1 = r2，我们还得到q1=q2，这说明商q与余数r是唯一的。

解析

定义1 

如果a和b为整数且a≠0，我们说a整除b是指存在整数c使得b=ac（b/a=c，注意，这里没说c不等于0，所以当b=0，c=0，a为任何数也可以，即b=ac，0=a*0）

如果a整除b，我们还称a是b的一个因子，且称b是a的倍数.

如果a整除b，则将其记为a | b（注意a<=b，值较小的写前面，较大的写后面），如果a不能整除b，则记其为a ∤b。

不能整除写法：一竖中间一横

定理1

如果a，b和c是整数，且a | b（b是a的倍数），b|c（c是b的倍数），则a|c.（c是a的倍数）

证明：因为a l b（b是a的倍数），b | c（c是b的倍数），故存在整数e和f，使得ae = b，bf = c。

因此c = bf = (ae)f = a(ef)（e，f是整数，相乘为整数，a乘了一个数才等于c，所以a较小，c较大），从而得到a | c

例如：因为11 | 66，66 | 198，故由定理1可知11 | 198

定理2

如果a，b，m和n为整数，且c | a（a是c的倍数），c | b（b是c的倍数），则c | (ma+nb).（ma+nb是c的倍数）

证明：因为c | a（a是c的倍数）且c | b（b是c的倍数），故存在整数e和f，使得a = ce，b = cf。

因此，ma + nb = mce + ncf = c(me + nf)（m，n，a，b是整数，相乘为整数，c乘了一个数才等于ma+nb，所以c较小，ma+nb较大），从而c | (ma+nb)。

例如：由于3 | 21，3 | 33，故由定理2可知3能够整除5*21 - 3*33  = 105 - 99 = 6。

定理3（********重点********）

带余除法 如果a和b是整数且b > 0，则存在唯一的整数q和r，使得a = bq + r,  0 ≤ r < b。

在带余除法给出的公式中，我们称q为商，r为余数，我们还称a为被除数，b为除数。

例如：如果a=133，b=21，则q=6，r=7，因为133-（21*6+7）=0且0<7<21。

类似地，如果a=-50，b=8，则q=-7，r=6，因为-50 = 8*(-7)+6且0<6<8.

我们注意到a能被b整除当且仅当在带余除法中的余数为0。

证明

a是被除数，b是除数，q是商，r是余数。  a/b=q...r

（1）存在性

考虑形如a-bk所有整数集合S，其中k为整数（可能为正数、0、负数）。设T是S中的所有非负整数构成的集合，T是非空（证明T集合里都是正数）的，因为当k是满足

k < a/b的整数时，a-bk是正的。（因为a-bk是正的  所以a-bk>0  所以a>bk  所以a/b>k   翻转一下就是 k<a/b）

T中有最小元r（最小数） = a-bq（余数  =  被除数-除数*商）。(q和r的值如定理中所述.)

根据r的构造可知 r ≥ 0（余数可能为0），且容易证明r < b。

（反证法）如果r≥b，则r > （ r-b = a - bq - b = a - b(q+1)） ≥ 0（不可能的情况，因为  b(q+1)>a  肯定成立，举例证明 ：

1.余数不为0情况。7/3=2...1   3*（2+1）=9    9>7     2.余数为0情况  14/7=2  7*(2+1)=21  21>14

这与我们选择r=a-bq为形如a-bk的整数中的最小元矛盾，因此0 ≤ r < b.（所以r不可能>=b，只可能<b ）

（2）唯一性

为了证明q和r的值是唯一（固定）的

我们假定有两个方程a=b*q1+r1和a=b*q2+r2，满足0 ≤ r1<b，o≤r2<b

把第二个方程从第一个方程中减去

可得0 = b(q1-q2)+(r1-r2). （b*q1+r1-(b*q2+r2)=a-a， b*q1+r1-b*q2-r2=0， b*（q1-q2）+（r1-r2）=0

因此，r2 - r1 = b(q1-q2)（ b*（q1-q2）+（r1-r2）=0     b*（q1-q2）= -（r1-r2）    b*（q1-q2）= r2-r1 ）

由此可知b整除r2-r1（ 可以用整体思想  r2-r1=a，q1-q2=c， a=bc  ，得b|a。 具体的   b | （r2-r1），因为b和（q1-q2）相乘，才等于（r2-r1）

，所以b小在前，r2-r1大在后）。

因为0≤r2<b，0≤r1<b，故-b<r2-r1<b（r2与r1相减，r2最小减r1最大，即0-b= -b   ，得出-b<r2-r1   ；   r2最大减r1最小，b-0=b，得出r2-r1<b 。

整理得 -b  <   r2-r2  <  b，所以r2-r1只能在-b~b这个区间内，不含-b和b，可以想象成数轴）

因此b可以整除r2-r1（-b~b这个区间（不含端点数），不可能出现b的倍数了）只有当r2 - r1=0，

（b|0即可，整除右边的数可以为0）

或者，换句话说，

当r1 = r2时，因为bq1+r1 = bq2+r2（根据上面的方程得知），且r1 = r2，我们还得到q1=q2，这说明商q与余数r是唯一的。