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仔细讨论.有兴趣的读者现在就可看这一部分内容.

以上五个例题的结论和证明方法是十分重要的，以后经常要用到.