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，并可推出其他的结论.