4.1　證明的第一個途徑

這一途徑是在通過用帶余數除法證明最小公倍數的性質——定理1——的基礎上實現的.但是由此不能證明定理8.

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

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

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

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

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

必要性設d₁，…，d_s是a₁，…，a_k的全體公約數，

L=［d₁，…，d_s］.

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

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

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

請讀者比較這一定理與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），詳細證明留給讀者.

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

（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的證明當m=0時，a=±1，結論顯然成立.當m≠0時，由2定理8，定理3和定理4可得

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

這就證明了所要的結論.

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

定理5和定理6是經常用到的.例如，當m是奇數時，由定理5推出（m，2^kb）=（m，b），而由定理6推出：若m|2^kb，則m|b.

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

定理7的證明先假定（a₁，a₂）=1.設L=［a₁，a₂］.由定理1知L|a₁a₂.另一方面，由a₁|L知L=a₁L′.進而由a₂|L=a₁L′及（a₂，a₁）=1，由定理6知a₂|L′.所以|a₁a₂||L.這樣，由2定理1（v）知L=|a₁a₂|.所以結論成立.當（a₁，a₂）≠1時，由2定理10的式（5）知

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

所以由已證結論知

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

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

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

下面來舉幾個例子.

例1設p是素數.證明：

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

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

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

這里A為一整數.由此及假設知結論對a=n+1也成立.這就證明了（ii）.應用定理6，由（ii）即推出（iii）.

（ii）和（iii）通常稱為Fermat小定理.這里的證明利用了二項式定理及結論（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設k是正整數.若一個有理數的k次方是整數，那么，這個有理數一定是整數.

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

例4設k是正整數.證明：

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

（ii）設a，b是正整數.若（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.請讀者解釋（ii）的意義.

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

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

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

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

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

這樣，m個余數r₀，r₁，…，r_m-1僅可能取m-1個值，其中必有兩個相等，設為r_i，r_k.不妨設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.關于δ_m（a）的性質將在第五章1仔細討論.有興趣的讀者現在就可看這一部分內容.

以上五個例題的結論和證明方法是十分重要的，以后經常要用到.