最大公約數(shù)重要性質(zhì)及推廣形式的應(yīng)用

【摘要】初等數(shù)論中，關(guān)于最大公約數(shù)的問題是競賽中的熱點(diǎn)之一.本文以一條重要性質(zhì)及推廣形式為基礎(chǔ)，討論了此性質(zhì)及推廣形式的應(yīng)用.

【關(guān)鍵詞】最大公約數(shù);重要性質(zhì);推廣形式;互素

1.重要性質(zhì)簡介

初等數(shù)論中，有一條重要的性質(zhì)：ax+by=(a，b).它表示對任意非零整數(shù)a，b存在一對整數(shù)x，y使得ax+by一定是a，b的最大公約數(shù).

證明如下:設(shè)非零整數(shù)a，b的最大公約數(shù)為n，則一定有n|a且n|b.a=k1n，b=k2n.

ax+by=(k1x+k2y)×n.當(dāng)k1x+k2y=1時(shí)，上述等式就取得a，b的最大公約數(shù).當(dāng)k1x+k2y≠1時(shí)，那ax+by=kn是最大公約數(shù)的整數(shù)倍.

性質(zhì)的第一種推廣形式是裴蜀等式，該等式實(shí)際上是該性質(zhì)的一種特殊形式，我們令(a，b)=1，即a，b互為素?cái)?shù)（以下簡稱互素），就可以得到著名的裴蜀等式ax+by=1.這也找到了判斷兩個(gè)整數(shù)互素的重要方法，即如果對于任意非零的兩個(gè)整數(shù)a，b，存在一組整數(shù)x，y使得ax+by=1成立，那么一定可以得出a，b互素.

證明如下：采用反證法，假設(shè)ax+by=1，a，b不互素.利用剛得出的第一條性質(zhì)可以得出ax+by=(k1x+k2y)×n=1.根據(jù)最大公約數(shù)的定義n一定為整數(shù)，所以得出(k1x+k2y)一定不是整數(shù)，顯然不成立.我們可以得出結(jié)論，只有一種情況是可能的:(k1x+k2y)=1，n=1這也說明了a，b一定互素.

重要性質(zhì)的第二種推廣形式：我們很容易從兩個(gè)數(shù)的判別方法得到三個(gè)數(shù)的方法.顯然存在ax+by+cz=(a，b，c)，與此同時(shí)也得到了三個(gè)數(shù)的裴蜀等式即ax+by+cz=1可以說明非零整數(shù)a，b，c互素，但值得注意的是不能說明三個(gè)整數(shù)之間兩兩互素.由此可以把性質(zhì)推廣到n個(gè)整數(shù)，即a1x1+a2x2+…+anxn=(x1，x2，…，xn)，a1x1+a2x2+…+anxn=1也是n個(gè)整數(shù)的裴蜀等式.

重要性質(zhì)的第三種推廣形式：即已知n個(gè)整數(shù)如何判斷它們兩兩互素.有前面的推廣形式，顯然a1x1+a2x2=1，a1x1+a2x2+a3x3=1，…，a1x1+a2x2+…+anxn=1一共有n-1個(gè)方程可以判斷出x1，x2，…，xn任意兩個(gè)整數(shù)都互素.

2.重要性質(zhì)及推廣形式的應(yīng)用

例1 對任意整數(shù)n，證明分?jǐn)?shù)21n+414n+3是即約分?jǐn)?shù).

分析 本題的實(shí)質(zhì)是證明21n+4和14n+3互質(zhì)，采用裴蜀等式可以很快的出結(jié)果.

觀察發(fā)現(xiàn)[21，14]=42，可以想到證明思路.

證明 利用裴蜀等式3×(14n+3)-2×(21n+4)=1，很快就可以說明題目中的分母與分子互素，所以是即約分?jǐn)?shù).

小結(jié) 如果不利用裴蜀等式，證明會(huì)變得比較困難.事實(shí)上，2×(21n+4)-3×(14n+3)=-1，也可以說明分子和分母互素.所以|ax+by|=1可以作為判定的條件.

例2 設(shè)n為正整數(shù)，證明:（n!+1，(n+1)!+1）=1.

分析 本題目和上面的例子類似，只是告訴我們在裴蜀等式的應(yīng)用過程中，選取x，y不一定是現(xiàn)實(shí)的數(shù)字，也有可能是一些抽象的整數(shù)，比如n.還有很重要的一點(diǎn)，在尋找裴蜀等式中的x，y得到ax+by=1有時(shí)候會(huì)很困難，所以需要借助一些輔助方法.

證明 根據(jù)第一條重要性質(zhì)，有(n+1)×(n!+1)-1×(n+1)!-1=n.顯然，n=(a，b).

一定有n|n!+1且n|(n+1)!+1，又因?yàn)閚|n!和n|(n+1)!，所以可以得到n|1，即n=1.

利用裴蜀等式很容易說明（n!+1，(n+1)!+1）=1.

總結(jié) 這里有一種數(shù)論中常用的方法，若n|a+b，且有n|a，一定可以得出n|b.利用此方法和其他方法結(jié)合可以解決很多棘手的問題.

例3 可以表示成1457x+1705y的最小正整數(shù)是多少？

分析 因?yàn)閷τ谛再|(zhì)一而言，本題從相反的角度來考慮問題.熟悉性質(zhì)的話不難想到ax+by=(a，b).問題迎刃而解，本質(zhì)為求兩個(gè)數(shù)的最小公約數(shù).

解 1705=5×11×31，1457=31×47，根據(jù)性質(zhì)可以知道(a，b)=31，答案為31.

小結(jié) 對性質(zhì)的靈活應(yīng)用，還有關(guān)鍵的一點(diǎn)看出11|341，先分解1705比較簡單.

例4 有一種盒子能裝3斤糖，另外一種盒子能裝6斤糖，假定每一個(gè)盒子必須裝滿，問：用這兩種盒子能裝完100斤糖嗎？

分析 應(yīng)用問題，利用最大公約數(shù)的性質(zhì)可以快速求解.

解 利用性質(zhì)3x+6y=k×(3，6)，（3，6）=3，3k≠100，所以這兩種盒子不可能裝完一百斤糖.

小結(jié) 生活中的數(shù)論應(yīng)用問題.

例5 設(shè)(a，b)=1，證明:(a+b，ab)=1.

分析 采用反證法證明，要充分利用a，b互素的已知條件.

證明 采用反證法.設(shè)(a+b，ab)=t，t為整數(shù)且不為1.因?yàn)檎麛?shù)a，b互素，且t|ab，t|a+b.

所以t=a或b或ab，否則與題意矛盾.

分三種情況分別討論：

(1)t=a時(shí)，由t|a+b可以得知t|b，（a，b）=t，t≠1，所以a與b不互素.與原題意矛盾.

(2)t=b時(shí)，同上可證.

(3)t=ab時(shí)，不妨設(shè)a+bab=k，1a+1b=k，可以設(shè)b=a+r，1a+r+1a=k，整理得關(guān)于a的方程ka2+(kr-2)×a-r=0，解為a=2-kr+S2k，S=k2r2+4，所以S一定是完全平方數(shù).

k2r2+4=u2，可以變形為k2r2-u2=4，（kr+u）×(kr-u)=4列出所有可能性：

kr+u=2和kr-u=2;kr+u=1和kr-u=4;kr+u=4和kr-u=1;三種情況下，第一組解得到kr=1，顯然排除，后兩組中u不是整數(shù)，排除.這就說明了(a+b，ab)=1.

總結(jié) 通過反證法不借助最大公約數(shù)的性質(zhì)也可以作出此題.

例6 設(shè)(a，b)=1，證明：(a2+b2，ab)=1.

分析 此題和上面的題目類似，采用性質(zhì)證明會(huì)比采用上面題目類似的證明簡單.

證明 和例題五類似，采用反證法，設(shè)(a2+b2，ab)=t≠1，利用a與b互素，可以同理證出前兩種情況，即t≠a，t≠b.

對于第三種情況，首先利用裴蜀等式，存在x，y使得ax+by=1.利用性質(zhì)可以得到如下等式:(a2+b2)×x2+2abxy=1，將ax+by=1代入，整理得1+b(x2-y2)=n，n是(a，b)的倍數(shù).

所以t|1+b(x2-y2)，由此，因?yàn)閠|b，所以t|1，得出矛盾.所以(a2+b2，ab)=1.

小結(jié) 可以發(fā)現(xiàn)，利用性質(zhì)可以很快的得出結(jié)論，比討論要方便得多.本題第三問也可用類似例題五的方法處理，也比較繁瑣.

例7 證明:(12n+5，9n+4，6n+3)=1.

分析 采用裴蜀等式的推廣形式.

證明 因?yàn)?×(9n+4)+1×(6n+3)-2×(12n+5)=1.所以原命題成立.

例8 證明:12n+5，9n+4，6n+3兩兩互質(zhì).

分析 利用性質(zhì)的推廣形式.

證明 顯然4×(9n+4)-3×(12n+5)=1，有例8的結(jié)論，可知原命題成立.

小結(jié) 裴蜀等式證明兩兩互質(zhì)，采用推廣形式比較方便.

性質(zhì)總結(jié) 最大公約數(shù)是初等數(shù)論中的一個(gè)重要概念，對ax+by這一性質(zhì)以及推廣形式的靈活應(yīng)用，解決問題可以起到事半功倍的效果.對于具體問題仍然要具體分析，多種方法、思想和性質(zhì)的聯(lián)合應(yīng)用也是解決難題的利器.

【參考文獻(xiàn)】

[1]余紅兵.數(shù)學(xué)競賽中的數(shù)論問題(第二版).上海：華東師范大學(xué)出版社，2005（6）:5-10.

[2]華羅庚學(xué)校.華羅庚學(xué)校數(shù)學(xué)試題解析高一年級(第三版).北京：中國大百科全書出版社，1996（3）:62-63.

[3]潘承洞，潘承彪.初等數(shù)論(第二版).北京：北京大學(xué)出版社，2009(12):12.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文