2　整除的基本知识

2.1　整除的定义与基本性质

定义1设a，b∈Z，a≠0.如果存在q∈Z，使得b=aq，那么就说b可被a整除，记做ab，且称b是a的倍数，a是b的约数（也可称为除数、因数）.b不能被a整除就记做a｜/b.

由定义及乘法运算的性质，立即可推出整除关系有下面性质（注意：符号ab本身包含了条件a≠0）.

定理1（i）ab⇔-ab⇔a-b⇔ab.

（ii）ab且bc⇒ac.

（iii）ab且ac⇔对任意的x，y∈Z，有abx+cy.

一般地，ab₁，…，ab_k同时成立⇔对任意的x₁，…，x_k∈Z，有ab₁x₁+…+b_kx_k.（iv）设m≠0，那么ab⇔mamb.

（v）ab且ba⇒b=±a.

（vi）设b≠0，那么ab⇒a≤b.

（vii）设a≠0，b=qa+c，那么a整除b的充分必要条件是a整除c.

证由b=aq⇔b=（-a）（-q）⇔-b=a（-q）⇔b=aq证明了（i）.因由b=aq₁和c=bq₂可推出c=a（q₁q₂），就证明了（ii）.由b=aq₁，c=aq₂可推出bx+cy=a（q₁x+q₂y），这就证明了（iii）的必要性.取x=1，y=0及x=0，y=1就可推出（iii）的充分性，一般结论的证明留给读者.由乘法相消律知，当m≠0时，

b=aq⇔mb=（ma）q，

这就证明了（iv）.由b=aq₁和a=bq₂就推出a=a（q₁q₂），由此及a≠0推出q₁q₂=1.所以q₁=±1.这就证明了（v）.由（i）知，从a|b可推出|b|=|a||q|.由b≠0知|q|≥1，这就证明了（vi）.（vii）的证明留给读者.

以上这些性质虽然十分简单，但却是十分重要的，它们是解决问题的基本思想、方法与技巧.下面举例说明.

例1证明：若3|n且7|n，则21|n.

证由3|n知n=3m，所以7|3m.由此及7|7m得7|（7m-2·3m）=m，因而有21|n.

例2设a=2t-1.（i）若a|2n，则a|n；（ii）若2｜ab，则2｜b.

证由a|2tn及2tn=an+n得a|（2tn-an），即a|n.这就证明了（i）.由于ab=2tb-b，b=2tb-ab，所以2|b.这就证明了（ii）.

例3设a，b是两个给定的非零整数，且有整数x，y，使得ax+by=1.证明：（i）若a|n且b|n，则ab|n.

（ii）若a|bn，则a|n.

证由n=n（ax+by）=（na）x+（nb）y，及ab|na，ab|nb，就推出ab|n，这就证明了（i）.注意到7·1+3·（-2）=1，由此也证明了例1.由byn=（1-ax）n，n=byn+axn就推出a|n.这就证明了（ii）.

例4设f（x）=a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀∈Z［x］，其中Z［x］表示全体一元整系数多项式组成的集合.若d|b-c，则

d|f（b）-f（c）.

特别地，有

b-c｜f（b）-f（c）.

证我们有

f（b）-f（c）=a_n（bⁿ-cⁿ）+a_n-1（b^n-1-c^n-1）+…+a₁（b-c），

由此及（b-c）|b^j-c^j，就推出所要结论.

由定义知，一个整数a≠0，它的所有倍数是

qa，q=0，±1，±2，…，

这个集合是完全确定的，通常记做

aZ.（1）

零是所有非零整数的倍数.但对于一个整数b≠0，关于它的约数一般就知道得不多了.显见，±1，±b（当b=±1时只有两个）一定是b的约数，它们称为b的显然约（因、除）数；b的其他的约数（如果有的话）称为b的非显然约（因、除）数或真约（因、除）数.由定理1（vi）知，b≠0的约数个数只有有限个.例如，b=12时，它的全体约数是：

±1，±2，±3，±4，±6，±12，

其中非显然约数有8个.b=7时，它的全体约数是

±1，±7，

它没有非显然约数.下面关于约数的性质是有用的.

定理2设整数b≠0，d₁，d₂，…，d_k是它的全体约数，那么b/d₁，b/d₂，…，b/d_k也是它的全体约数.也就是说，当d遍历b的全体约数时，b/d也遍历b的全体约数.此外，若b＞0，则当d遍历b的全体正约数时，b/d也遍历b的全体正约数.

证当d_j|b时，b/d_j是整数，b=d_j（b/d_j），所以b/d_j也是b的约数，且当d_i≠d_j时，b/d_i≠b/d_j.这样，b/d₁，…，b/d_k是k个两两不同的b的约数.由于b的约数的个数是一定的，这就证明了第一个结论.只要注意到b的正约数的个数也是一定的（由定理1（i）知，所有的约数中一半是正的、一半是负的），由同样的讨论就推出第二个结论.

例如，当b=12时，我们有

d=±1，±2，±3，±4，±6，±12.

b/d=±12，±6，±4，±3，±2，±1.