最大公因數(shù)與最小公倍數(shù)

張新春

1.最大公因數(shù)

若d是a的因數(shù)，也是b的因數(shù)，我們就稱(chēng)d是a，b的公因數(shù)。a，b的公因數(shù)中最大的一個(gè)，叫做a，b的最大公因數(shù)。記為（a，b）或GCD（a，b）。

我們可以把最大公因數(shù)的定義寫(xiě)得正式一點(diǎn)。

d是a，b的最大公因數(shù)，當(dāng)且僅當(dāng)：（1）d|a，d|b；（2）若c|a，c|b，則c臆d。

有幾個(gè)問(wèn)題需要討論一下：（1）任意的兩個(gè)數(shù)a，b都有公因數(shù)嗎？（2）a，b的公因數(shù)中一定有一個(gè)最大的嗎？

對(duì)于問(wèn)題（1），由于1是任何數(shù)的因數(shù)，所以對(duì)任意兩個(gè)數(shù)a，b，1都是它們的公因數(shù)。從而任意的兩個(gè)數(shù)a，b都有公因數(shù)。對(duì)于問(wèn)題（2），若a，b不同時(shí)為0，當(dāng)a是正數(shù)時(shí)，a的因數(shù)最大者為a，當(dāng)a是負(fù)數(shù)時(shí)，a的因數(shù)最大者為-a；對(duì)于b也可以作類(lèi)似的討論。也就是說(shuō)，對(duì)任意不同時(shí)為0的a，b，它們的公因數(shù)總是小于a，-a，b，-b這四個(gè)數(shù)中的最大者，從而總是有最大公因數(shù)。

需要注意的是，a，b可以任意為正為負(fù)，但不能同時(shí)為0，即（0，0）是沒(méi)有意義的。

若兩個(gè)數(shù)的最大公因數(shù)為1，我們稱(chēng)這兩個(gè)數(shù)為互質(zhì)數(shù)，或稱(chēng)這兩個(gè)數(shù)互質(zhì)（或互素）。

（2）a，b的任意公因數(shù)都是a，b的最大公因數(shù)的因數(shù)。

在小學(xué)數(shù)學(xué)教材中，找兩個(gè)數(shù)的最大公因數(shù)通常都是用列舉的辦法。即分別找出兩個(gè)數(shù)的因數(shù)，再找出公共的因數(shù)，然后找出最大的一個(gè)。這種方法盡管效率不高，卻是一種最樸素的方法，應(yīng)用范圍也最廣，蘊(yùn)含著一些基本的數(shù)學(xué)思想方法（列舉、集合的思想等）。我們需要正確認(rèn)識(shí)其價(jià)值。當(dāng)然，在此基礎(chǔ)上，若能讓學(xué)生學(xué)會(huì)一些比較高效的方法也是有價(jià)值的。

2.最小公倍數(shù)

兩個(gè)整數(shù)a，b的最小公倍數(shù)，是指能同時(shí)被a，b整除的數(shù)中的最小正整數(shù)。通常記為[a，b]。而能同時(shí)被a，b整除的數(shù)也叫a，b的公倍數(shù)。

有一個(gè)結(jié)論：a，b的任意公倍數(shù)都是其最小公倍數(shù)的倍數(shù)。比如15和10的最小公倍數(shù)是30，那么15和10的任何公倍數(shù)都應(yīng)該是30的倍數(shù)。這一點(diǎn)不難檢驗(yàn)。問(wèn)題是如何在一般情況下證明這個(gè)結(jié)論？我們只需要證明a，b的任意正的公倍數(shù)都是其最小公倍數(shù)的倍數(shù)即可。為此，我們?cè)O(shè)m是a，b的最小公倍數(shù)而N是a，b的任意正的公倍數(shù)。我們要證明N是m的倍數(shù)。事實(shí)上，由于m是a，b的最小公倍數(shù)而N是a，b的正的公倍數(shù)，因此，N不小于m，從而N-m應(yīng)該為a，b的公倍數(shù)（一個(gè)數(shù)的兩個(gè)倍數(shù)之差仍為這個(gè)數(shù)的倍數(shù)）。且N-m不小于0。若考慮N-m，N-2m，N-3m…以上數(shù)列終于會(huì)從某一個(gè)開(kāi)始小于0。

設(shè)N-xm是最后一個(gè)大于0的。這就是說(shuō)N-xm大于0，而N-xm再減去一個(gè)m就不大于0了（注意，不一定是小于0）。于是N-xm不大于m，但m是a，b的最小公倍數(shù)，從而N-xm不可能小于m，于是只有N-xm=m。從而N是m的倍數(shù)。

最小公倍數(shù)的求法可由下列結(jié)論轉(zhuǎn)化為最大公因數(shù)的求法。

兩個(gè)整數(shù)a，b的最小公倍數(shù)[a，b]和最大公因數(shù)（a，b）滿(mǎn)足[a，b]=（a，b）=a×b，即兩個(gè)數(shù)的最大公因數(shù)與最小公倍數(shù)的乘積等于這兩個(gè)數(shù)的乘積。

3.線(xiàn)性不定方程

我們知道，兩個(gè)整數(shù)a，b的最大公因數(shù)，就是所有形如ax+by的正整數(shù)中最小的一個(gè)。并且，所有形如ax+by的數(shù)，都是a，b的最大公因數(shù)的倍數(shù)。比如a=78，b=30，則a，b的最大公因數(shù)為6。由歐幾里得算法，可以找到這樣的x，y，使得78x+30y=6。

事實(shí)上，78=30×2+18，30=18×1+12，18=12×1+6，12=6×2+0。由此可以得到6=18-12×1。我們需要把其中的18和12用含有78和30的式子表示，這樣就可以把6寫(xiě)成形如78x+30y的形式。而由上面的式子可知18=78-30×2，12=30-18=30-（78-30×2）=30×3-78。于是，6=18-12×1=78-30×2-（30×3-78）=78×2-30×5 =78×2+30×（-5）。

像78x+30y=6這樣未知數(shù)個(gè)數(shù)超過(guò)一個(gè)的方程叫不定方程。這個(gè)不定方程也叫線(xiàn)性不定方程，線(xiàn)性是指方程的未知數(shù)的次數(shù)為1，之所以說(shuō)是“線(xiàn)性”，很重要的原因是像78x+30y=6這樣的方程，在幾何上就表示一條直線(xiàn)。不定方程通常有很多解，我們往往關(guān)心滿(mǎn)足一定條件的解，比如整數(shù)解，特別是正整數(shù)解。

我們還可以證明，方程ax+by=1的所有整數(shù)解都可以寫(xiě)成這種形式。

于是，求不定方程ax+by=1（a，b互質(zhì)）整數(shù)解的問(wèn)題就得到完全的解決。

考慮一般的問(wèn)題，形如ax+by=n（n為整數(shù)，a，b互質(zhì)）的整數(shù)解如何求呢？只要求出ax+by=1（a，b互質(zhì)）的解，再乘n就可以了。

考慮更一般的問(wèn)題，若不定方程ax+by=n中的a，b不互質(zhì)呢？我們不難想到，若這個(gè)方程有整數(shù)解，n一定能被a，b的最大公因數(shù)整除（事實(shí)上，比如方程78x+30y=9就不可能有整數(shù)解，因?yàn)閷?duì)任意的整數(shù)x，y，78x+30y都是6的倍數(shù)，而不會(huì)是9），此時(shí)，只要用a，b的最大公因數(shù)去除這個(gè)方程的兩邊，即可把這個(gè)方程轉(zhuǎn)化為上述研究過(guò)的方程。

于是，對(duì)于任意有整數(shù)解的不定方程，我們已經(jīng)得到了求其所有整數(shù)解的方法。

在以上討論不定方程的過(guò)程中，我們先研究特殊情況，再設(shè)法把一般情況轉(zhuǎn)化為特殊情況。這是數(shù)學(xué)研究常用的方法，在小學(xué)數(shù)學(xué)教學(xué)中也應(yīng)該適當(dāng)?shù)貪B透這種方法。endprint