【整数的可除性】

1、带余数除法。若a、b是两个整数，其中b>0，则存在着两个整数q及r，使得a=bq+r，0<=r<b成立，而且q及r是惟一的。

　　这里要注意，b>0，且b>r>=0。所以对于（-1）%7，r应该是6。理论上不应该存在b为负数的情况。　　

　　b | a，意为b整除a。 a = bt。

2、a是b的倍数，b是c的倍数，则a是c的倍数。

3、若a+b是m的倍数，则a-b也是m的倍数。

4、若a1、a2、a3...an都是m的倍数，q1、q2、q2...qn是任意的整数，则q1a1+q2a2+q3a3+...+qnan是m的整数。4）是3）的推论。

5、a、b的最大公因数记作(a,b)。最小公倍数记作[a,b]。

6、0与b的公因数就是b，因为0=0*b，任何数都是0的因数。(0, b) = b。

　  0没有倍数，因为0*x=0，0乘任何数都为0。

7、a,b的公因数与(a,b)的因数相同。反证法可证。

8、a = bq +c，则（a,b）= (b,c)。此为欧几里德法。

9、（am,bm） = (a,b)m

10、a,b是任意两个不全为零的数，则存在两个数s,t，使得：as+bt=(a,b)

11、若(a,c)=1，则(ac,b)等于(c,b)。即a不影响c的最大公约数运算。

12、若c|ab，且(a,c)=1，则c|b。

13、a,c的最小公倍数记为[a,b]。若(a,c)=1，[a,c] = ac。

14、a是任一大于1的整数，则a的除1外的最小正因数q是质数，并且工是合数时q<=sqrt(a)。

15、任一大于1的整数a，能被表示成 p1p2p3p4，其中p1<=p2<=p3<=p4。如果写成p1^x*p2^x*p3^x，其中p1<p2<p3，则此式叫标准分解式。

16、任意一个数，[x]记作x的整数部分，{x}记作x的小数部分。

17、[x] + [y] <= [x+y]，{x}+{y}>={x+y}

18、若ax0+by0是形如ax+by的数中的最小的正数，则(ax0+by0)|(ax+by)。类似地，推广到N个数的形式也成立。

　　因为，ax+by = q(ax0+by0)+r。

　　得出，r = a(x-qx0)+b(y-y0)，显然r是ax+by集合中的数，r比ax0+by0小，则只能是0。

　　得出，ax+by = q(ax0+by0)，所以任意的 (ax0+by0) | (ax+by)。

19、若（a1,a2)=d2, (d2,a3)=d3,...,(dn-1,an)=dn。则(a1,a2,...an)=dn。

　　首先由后往前，证明 dn是所有a1,a2..an的因数。

　　其次，从前往后证明，所有的其它因数d都整除dn，即d<=dn。

　　即可得dn是a1,a2,...an的最大公约数。

20、若[a1,a2]=d2, [d2,a3]=d3,...,[dn-1,an]=dn。则[a1,a2,...an]=dn。

21、质数是指大于1的正整数，即1不是质数。

22、p是一质数，a是任意整数，则a能被p整除或互质。

整数的可除性