4.1　證明的第一個(gè)途徑

這一途徑是在通過用帶余數(shù)除法證明最小公倍數(shù)的性質(zhì)——定理1——的基礎(chǔ)上實(shí)現(xiàn)的.但是由此不能證明定理8.

定理1的證明充分性是顯然的.下證必要性.設(shè)L=［a₁，…，a_k］.由3定理1知，有q，r使得

c=qL+r，0≤r＜L.

由此及a_j|c推出a_j|r（1≤j≤k），所以r是公倍數(shù).進(jìn)而，由最小公倍數(shù)的定義及0≤r＜L就推出r=0，即L|c，這就證明了必要性.結(jié)論表明：公倍數(shù)一定是最小公倍數(shù)的倍數(shù).

定理1刻畫了最小公倍數(shù)的本質(zhì)屬性，“最小”的含義實(shí)際上不是指“大小”，而是指它一定是任一公倍數(shù)的約數(shù)，是公倍數(shù)在整除意義下的“最小”.這可以作為最小公倍數(shù)的定義，但這時(shí)它的存在性則需證明.

定理2的證明充分性由（i）知D是a_j（1≤j≤k）的公約數(shù)，由（ii），2定理1（vi）及D≥1知，a_j（1≤j≤k）的任一公約數(shù)d有|d|≤D.因而由定義知D是a₁，…，a_k的最大公約數(shù).

必要性設(shè)d₁，…，d_s是a₁，…，a_k的全體公約數(shù)，

L=［d₁，…，d_s］.

由定理1知L|a_j（1≤j≤k），因此，L滿足條件（i）和（ii）（取D=L）.因而，由上面證明的充分性知L=（a₁，…，a_k）=D.這就證明了必要性.結(jié)論表明：公約數(shù)一定是最大公約數(shù)的約數(shù).

定理2刻畫了最大公約數(shù)的本質(zhì)屬性，“最大”的含義實(shí)際上不是指“大小”，而是指它一定是任一公約數(shù)的倍數(shù)，是公約數(shù)在整除意義的“最大”.這可以作為最大公約數(shù)的定義，但這時(shí)它的存在性則需證明.

定理3的證明在2定理10中取a_j=mb_j（1≤j≤k），由定理2就推出m|（a₁，…，a_k）.因此2式（4）成立，即式（1）成立.證畢.

請(qǐng)讀者比較這一定理與2定理10的差別.

定理4的證明我們來證（i）.若d|a_j（1≤j≤k），則由定理2（k=2）知，d|（a₁，a₂），d|a_j（3≤j≤k）；反過來，若d|（a₁，a₂），d|a_j（3≤j≤k），則由定義知，d|a_j（1≤j≤k）.這就是證明了

D（a₁，a₂，a₃，…，a_k）=D（（a₁，a₂），a₃，…，a_k）.

所以（i）成立.由（i）即推出（ii），詳細(xì)證明留給讀者.

定理4表明：多個(gè)數(shù)的最大公約數(shù)，可以由求兩個(gè)數(shù)的最大公約數(shù)來逐步求出.定理3表明：求一組數(shù)的最大公約數(shù)時(shí)可以通過提出這組數(shù)的公約數(shù)的方法來逐步求出.這些正是我們所熟知的求最大公約數(shù)的方法，這里給出了嚴(yán)格的證明.例如：

（12，18）=2·（6，9）=2·3·（2，3）=6·（2，3-2）=6·（2，1）=6.

這里還用到了2定理8.再例如，

（6，10，-15）=（（6，10），15），

（6，10）=2·（3，5）=2·（3，5-2·3）=2·（3，-1）=2，

（2，15）=（2，15-2·7）=（2，1）=1.

由以上三式得（6，10，-15）=1.再例如

（10，45，9，84）=（（10，45），（9，84））=（5（2，9），3（3，28））=（5，3）=1.

由定理3和定理4容易證明（留給讀者）：

（a₁，a₂）（b₁，b₂）=（a₁b₁，a₁b₂，a₂b₁，a₂b₂），

以及一般地

（a₁，…，a_r）（b₁，…，b_s）=（a₁b₁，…，a₁b_s，…，a_rb₁，…，a_rb_s）.

定理5的證明當(dāng)m=0時(shí)，a=±1，結(jié)論顯然成立.當(dāng)m≠0時(shí)，由2定理8，定理3和定理4可得

（m，b）=（m，b（m，a））=（m，（mb，ab））=（m，mb，ab）=（m，ab）.

這就證明了所要的結(jié)論.

定理6的證明由2定理8，定理5得|m|=（m，ab）=（m，b），這就推出m|b.

定理5和定理6是經(jīng)常用到的.例如，當(dāng)m是奇數(shù)時(shí)，由定理5推出（m，2^kb）=（m，b），而由定理6推出：若m|2^kb，則m|b.

定理6常用形式是：若（m₁，m₂）=1，m₁|n，m₂|n，則m₁m₂|n.這因?yàn)橛蒻₁|n知n=m₁n₁，由此利用條件（m₂，m₁）=1，從定理6推出m₂|n₁，因而m₁m₂|n.一般地可證明以下結(jié)論（留給讀者）：若m₁，…，m_k兩兩既約，m_j|n（1≤j≤k），則m₁…m_k|n.

定理7的證明先假定（a₁，a₂）=1.設(shè)L=［a₁，a₂］.由定理1知L|a₁a₂.另一方面，由a₁|L知L=a₁L′.進(jìn)而由a₂|L=a₁L′及（a₂，a₁）=1，由定理6知a₂|L′.所以|a₁a₂||L.這樣，由2定理1（v）知L=|a₁a₂|.所以結(jié)論成立.當(dāng)（a₁，a₂）≠1時(shí)，由2定理10的式（5）知

（a₁/（a₁，a₂），a₂/（a₁，a₂））=1，

所以由已證結(jié)論知

由此及2定理12（k=2，m=（a₁，a₂））即得所要結(jié)論.

定理7刻畫了最大公約數(shù)與最小公倍數(shù)之間的關(guān)系.我們可以通過求出最大公約數(shù)來求得最小公倍數(shù).但是，這定理對(duì)三個(gè)及三個(gè)以上數(shù)的情形是不成立的.這可見習(xí)題四第一部分的第10題.

以上我們?cè)趲в鄶?shù)除法的基礎(chǔ)上建立了最大公約數(shù)與最小公倍數(shù)理論.但應(yīng)該指出的是，除了定理1的證明中用到了帶余數(shù)除法外，其他結(jié)論都是在定理1的基礎(chǔ)上，從定義出發(fā)僅利用1和2中的性質(zhì)來證明的，沒有用到帶余數(shù)除法.這種論證的方法與技巧在整除理論中是十分基本和重要的.還要指出的是，在由定理1推出定理2之后，定理3～定理6的證明都只用到定理2而不需要定理1.也就是說，由定理2成立，僅利用1和2中的性質(zhì)就可證明定理3～定理6.

下面來舉幾個(gè)例子.

例1設(shè)p是素?cái)?shù).證明：

是整數(shù)，即j！（p-j）！|p！（這是用到了排列組合理論中的結(jié)果，在7推論4將直接證明這結(jié)論）.由于p是素?cái)?shù)，所以，對(duì)任意1≤i≤p-1有（p，i）=1.因此由定理5知

（p，j！（p-j）！）=1，1≤j≤p-1.

進(jìn)而由定理6推出：當(dāng)1≤j≤p-1時(shí)j！（p-j）！|（p-1）！，這就證明了（i）.用歸納法來證（ii）.a=1時(shí)顯然成立.假設(shè)a=n時(shí)成立.當(dāng)a=n+1時(shí)，利用二項(xiàng)式定理，由（i）知

這里A為一整數(shù).由此及假設(shè)知結(jié)論對(duì)a=n+1也成立.這就證明了（ii）.應(yīng)用定理6，由（ii）即推出（iii）.

（ii）和（iii）通常稱為Fermat小定理.這里的證明利用了二項(xiàng)式定理及結(jié)論（i），在第三章3定理3將給出更簡單直接的證明.

例2

證明：（i）（a，uv）=（a，（a，u）v）；

（ii）（a，uv）|（a，u）（a，v）；

（iii）若（u，v）=1，則（a，uv）=（a，u）（a，v）.

證由2定理8（i）和（iii），定理4及定理3即得

（a，uv）=（a，uv，av）=（a，（uv，av））=（a，（a，u）v）.

由定理2及定理3得

（a，（a，u）v）|（（a，u）a，（a，u）v）=（a，u）（a，v）.

由此及（i）即得（ii）.顯見，（i）是定理5的推廣.（iii）的證明留給讀者.

例3設(shè)k是正整數(shù).若一個(gè)有理數(shù)的k次方是整數(shù)，那么，這個(gè)有理數(shù)一定是整數(shù).

證不妨設(shè)這個(gè)有理數(shù)是b/a，a≥1，（a，b）=1.若（b/a）^k=c是整數(shù)，則ca^k=b^k，所以a|b^k.由于（a，b）=1，所以由定理6知a|b，因而1=（a，b）=a.這就證明了所要的結(jié)果.

例4設(shè)k是正整數(shù).證明：

（i）（a^k，b^k）=（a，b）^k；

（ii）設(shè)a，b是正整數(shù).若（a，b）=1，ab=c^k，則

a=（a，c）^k，b=（b，c）^k.

證由定理3得

由這及第一式就推出（i）.下面證（ii）.由定理5及（a，b）=1知（a^k-1，b）=1，因而由定理3知

a=a（a^k-1，b）=（a^k，ab）=（a^k，c^k）=（a，c）^k，

最后一步用到了（i）.類似證b=（b，c）^k.請(qǐng)讀者解釋（ii）的意義.

例5設(shè)m≥2，（m，a）=1.證明：

（i）存在正整數(shù)d≤m-1，使得m|a^d-1.

（ii）設(shè)d₀是滿足（i）的最小正整數(shù)d，那么m|a^h-1（h≥1）的充分必要條件是d₀|h.我們記d₀為δ_m（a），稱為a對(duì)模m的指數(shù).

證由m≥2，（m，a）=1知m｜/a，由此及（m，a）=1，從定理6推出m｜/a^j，j≥1.進(jìn)而，由3定理1知

a^j=q_jm+r_j，0＜r_j＜m.

這樣，m個(gè)余數(shù)r₀，r₁，…，r_m-1僅可能取m-1個(gè)值，其中必有兩個(gè)相等，設(shè)為r_i，r_k.不妨設(shè)0≤i＜k＜m，因而有

m（q_k-q_i）=a^k-aⁱ=aⁱ（a^k-i-1）.

由此從定理6推出m|a^k-i-1，取d=k-i即證明了（i）.

（ii）的證明和3例5（ii）的證明完全相同，只要把那里的2換為a.關(guān)于δ_m（a）的性質(zhì)將在第五章1仔細(xì)討論.有興趣的讀者現(xiàn)在就可看這一部分內(nèi)容.

以上五個(gè)例題的結(jié)論和證明方法是十分重要的，以后經(jīng)常要用到.