4.2　證明的第二個途徑

我們已經指出可以由2式（3）給出的集合——由a₁，…，a_k的整系數線性組合構成——來刻畫最大公約數（a₁，…，a_k）.現在我們利用帶余數除法來給出它們之間的明確聯系，即證明定理8，由此推出其他七個定理，實現建立最大公約數理論的第二個途徑.

定理8的證明由于0＜a²₁+…+a²_k∈S，所以集合S中有正整數.由最小自然數原理知S中必有最小正整數，設為s₀.顯見，對任一公約數d|a_j（1≤j≤k）必有d|s₀，所以|d|≤s₀.另一方面，對任一a_j由帶余數除法知

a_j=q_js₀+r_j，0≤r_j＜s₀.

顯見r_j∈S.若r_j＞0，則和s₀的最小性矛盾.所以，r_j=0，即s₀|a_j（1≤j≤k）.因此，s₀是最大公約數.s₀當然是式（2）右邊的形式.證畢.

由定理8推出定理2是顯然的.

定理2的證明顯見，只要證必要性。（i）由定義知成立，而（ii）由表示式（2）直接看出（事實上，在定理8的證明中，是先指出s₀滿足條件（i）和（ii））.

顯見，定理8所包含的信息要比定理2豐富得多.在證明了定理2后，我們當然可以像第一個途徑那樣來證明定理3～定理6.由于最大公約數能表為式（2）的形式這一結論是十分重要的（雖然這里只是說x_1，0，…，x_k，0存在并沒有指出如何求x_1，0，…，x_k，0，而且顯然不是唯一的），因為這使得我們在論證它們的性質的過程中有了一個便于推導的表示式，而用不著總是從定義出發，需要較高的技巧.為了說明這一點，下面我們利用定理8來直接給出定理3～定理6的證明，以及進而給出定理1和定理7的證明.這就是第二個途徑.

定理3的證明由定理8知，可設

（b₁，…，b_k）=b₁y₁+…+b_ky_k，

（mb₁，…，mb_k）=（mb₁）x₁+…+（mb_k）x_k.

這樣，根據這兩式，由m（b₁，…，b_k）|mb_j（1≤j≤k）推出

m（b₁，…，b_k）|（mb₁，…，mb_k）；

由（mb₁，…，mb_k）|mb_j（1≤j≤k），推出

（mb₁，…，mb_k）|（mb₁）y₁+…+（mb_k）y_k=m（b₁，…，b_k）.

由以上兩式就證明了所要結論.

定理4的證明先證（i）.由定理8知，可設

D₁=（a₁，…，a_k）=a₁x₁+…+a_kx_k，

D₂=（a₁，a₂）=a₁y₁+a₂y₂，

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

由D₃|（a₁，a₂），D₃|a_j（3≤j≤k）知D₃|a_j（1≤j≤k），所以D₃|D₁.注意到

D₃=a₁（y₁z₂）+a₂（y₂z₂）+a₃z₃+…+a_kz_k

及D₁|a_j（1≤j≤k），就推出D₁|D₃.所以D₁=D₃.同樣的方法可證（ii），具體推導留給讀者.

定理5的證明由定理8知，可設

（m，b）=mx₁+bx₂，（m，ab）=my₁+（ab）y₂.

由（m，b）|m，（m，b）|b及第二式就推出（m，b）|（m，ab）.由條件及定理8知，存在z₁，z₂，使

mz₁+az₂=1，（3）

因而有

（m，b）=（mx₁+bx₂）（mz₁+az₂）=m（mx₁z₁+ax₁z₂+bx₂z₁）+（ab）（x₂z₂）.

由此及（m，ab）|m，（m，ab）|ab就推出（m，ab）|（m，b）.這就證明了定理.

定理6的證明由定理8及條件知有式（3）成立.所以，有m（bz₁）+（ab）z₂=b.由此及m|ab即得m|b.

應該指出的是：在上述定理2～定理6的證明中，除了整除最基本的性質（2定理1）之外，都只用了定理8而不需要其他結論.下面來證定理7和定理1.

定理7的證明只要證a₁＞0，a₂＞0的情形（為什么）.先設（a₁，a₂）=1.由a₁|［a₁，a₂］，a₂|［a₁，a₂］及定理6知，a₁a₂|［a₁，a₂］.由定義知［a₁，a₂］≤a₁a₂，所以［a₁，a₂］=a₁a₂.當（a₁，a₂）>1時證明與第一個途徑中的定理7的證明相同.證畢.

定理1的證明設l是a₁，a₂的公倍數.由a₁/（a₁，a₂）|l/（a₁，a₂），a₂/（a₁，a₂）|l/（a₁，a₂）及（a₁/（a₁，a₂），a₂/（a₁，a₂））=1，利用定理6及定理7推出［a₁/（a₁，a₂），a₂/（a₁，a₂）］=a₁a₂/（a₁，a₂）²|l/（a₁，a₂）.由此及2定理12得［a₁，a₂］|l.這證明了k=2時結論成立.由此用歸納法就可證明定理也可以用反證法及最小自然數原理來證.請讀者考慮..詳細推導留給讀者.

下面來舉例說明定理8的應用.

例6若（a，b）=1，則任一整數n必可表示為

n=ax+by，x，y是整數.

由（a，b）=1及定理8知，存在x₀，y₀，使ax₀+by₀=1.因此，取x=nx₀，y=ny₀即滿足要求.

例7設a，b是整數，11｜/a.證明：11｜/a²+5b².

證用反證法.若11|a²+5b²，則由11｜/a推出11｜/b（為什么）.因此由定理8知，必有x，y，使

11x+by=1.

由此及11|y²（a²+5b²）=（ay）²+5（by）²推出

11|（ay）²+5.

但對所有的y，（ay）²被11除后所得的余數必在0，1，4，9，5，3中，所以上式不可能成立.因此必有11｜/a²+5b².以上討論也表明：11|a²+5b²的充分必要條件是11|a，11|b.

本題也可以用下面的方法直接證明：x²被11除后所得的余數必在0，1，4，9，5，3中.容易直接驗證，當r²，s²被11除后所得余數的取值均為0，1，4，9，5，3，且不同時為零時，必均有

11｜/r²+5s².

由此即推出所要結論.但這個方法所需作的直接驗算比上面的方法要多一倍以上.

例8設n，k是正整數，（k，n）=1，0＜k＜n.再設集合M=｛1，2，…，n-1｝.現對集合M中的每個數i涂上藍色或白色，要滿足以下條件：（i）i和n-i要涂上同一種顏色；（ii）當i≠k時，i和|k-i|要涂上同一種顏色.證明：所有的數一定都涂上同一種顏色.

證我們來證明：所有的i∈M必和k同色.由例6知存在x，y，使

i=xk+yn.

由1≤i≤n-1知，x，y的取值可能出現三種情形：

（a）x＞0，y=0；（b）x＞0，y＜0；（c）x＜0，y＞0.

在情形（a），由條件（ii）知i和k同色.

在情形（c），由條件（i）知i和n-i=（-x）k+（-y+1）n同色.若-y+1=0這就變為情形（a），若-y+1＜0這就變為（b）.所以只要討論情形（b）.

在情形（b）必有x＞-y.這時又可分三種情形：①k=i；②k＞i；③k＜i.當①出現時結論成立.當③出現時，由帶余數除法知

i=qk+i′，0≤i′＜k.

若i′=0，變為情形（a），結論成立.若1≤i′＜k，由條件（ii）知，i和i′=i-qk=（x-q）k+yn同色，代替i考慮i′就變為情形②.當②出現時，由條件（ii）知，i和k-i=（-x+1）k-yn同色，再由條件（i）知i和i″=n-（k-i）=（x-1）k+（y+1）n同色.若y+1=0，則結論成立；若y+1＜0，則又變為情形（b），繼續對i″分①，②，③三種情形考慮.注意到y<y+1=y′<0，這樣，討論若干步后，總可得到i^*=x^*k（x^*為某個正整數），故i^*與k同色，即i與k同色.證畢.

定理8僅指出了x_1，0，…，x_k，0的存在性，在4.3小節將討論如何求x₁，0，…，x_k，0的算法.

容易看出，以上兩個途徑都是在證明了定理2——最大公約數的本質屬性——的基礎上，再證明定理3～6，建立最大公約數理論的.在第一個途徑我們是首先證明了定理1——最小公倍數的本質屬性——來推出定理2，但得不到定理8中的最大公約數的明確表示式（2）；在第二個途徑則是先證明了定理8中的式（2），它包含了定理2，并可推出其他的結論.