2　整除的基本知識

2.1　整除的定義與基本性質(zhì)

定義1設a，b∈Z，a≠0.如果存在q∈Z，使得b=aq，那么就說b可被a整除，記做ab，且稱b是a的倍數(shù)，a是b的約數(shù)（也可稱為除數(shù)、因數(shù)）.b不能被a整除就記做a｜/b.

由定義及乘法運算的性質(zhì)，立即可推出整除關系有下面性質(zhì)（注意：符號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）的證明留給讀者.

以上這些性質(zhì)雖然十分簡單，但卻是十分重要的，它們是解決問題的基本思想、方法與技巧.下面舉例說明.

例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是兩個給定的非零整數(shù)，且有整數(shù)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］表示全體一元整系數(shù)多項式組成的集合.若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，就推出所要結論.

由定義知，一個整數(shù)a≠0，它的所有倍數(shù)是

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

這個集合是完全確定的，通常記做

aZ.（1）

零是所有非零整數(shù)的倍數(shù).但對于一個整數(shù)b≠0，關于它的約數(shù)一般就知道得不多了.顯見，±1，±b（當b=±1時只有兩個）一定是b的約數(shù)，它們稱為b的顯然約（因、除）數(shù)；b的其他的約數(shù)（如果有的話）稱為b的非顯然約（因、除）數(shù)或真約（因、除）數(shù).由定理1（vi）知，b≠0的約數(shù)個數(shù)只有有限個.例如，b=12時，它的全體約數(shù)是：

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

其中非顯然約數(shù)有8個.b=7時，它的全體約數(shù)是

±1，±7，

它沒有非顯然約數(shù).下面關于約數(shù)的性質(zhì)是有用的.

定理2設整數(shù)b≠0，d₁，d₂，…，d_k是它的全體約數(shù)，那么b/d₁，b/d₂，…，b/d_k也是它的全體約數(shù).也就是說，當d遍歷b的全體約數(shù)時，b/d也遍歷b的全體約數(shù).此外，若b＞0，則當d遍歷b的全體正約數(shù)時，b/d也遍歷b的全體正約數(shù).

證當d_j|b時，b/d_j是整數(shù)，b=d_j（b/d_j），所以b/d_j也是b的約數(shù)，且當d_i≠d_j時，b/d_i≠b/d_j.這樣，b/d₁，…，b/d_k是k個兩兩不同的b的約數(shù).由于b的約數(shù)的個數(shù)是一定的，這就證明了第一個結論.只要注意到b的正約數(shù)的個數(shù)也是一定的（由定理1（i）知，所有的約數(shù)中一半是正的、一半是負的），由同樣的討論就推出第二個結論.

例如，當b=12時，我們有

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

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