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.