最大公因數與最小公倍數

文︳張新春

最大公因數與最小公倍數

文︳張新春

1.最大公因數

若d是a的因數，也是b的因數，我們就稱d是a，b的公因數。a，b的公因數中最大的一個，叫做 a，b 的最大公因數。記為（a，b）或 GCD（a，b）。

我們可以把最大公因數的定義寫得正式一點。

d 是 a，b 的最大公因數，當且僅當：（1）d|a，d|b；（2）若 c|a，c|b，則 c≤d。

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

對于問題（1），由于1是任何數的因數，所以對任意兩個數a，b，1都是它們的公因數。從而任意的兩個數a，b都有公因數。對于問題（2），若a，b不同時為0，當a是正數時，a的因數最大者為a，當a是負數時，a的因數最大者為-a；對于b也可以作類似的討論。也就是說，對任意不同時為0的a，b，它們的公因數總是小于 a，-a，b，-b 這四個數中的最大者，從而總是有最大公因數。

需要注意的是，a，b可以任意為正為負，但不能同時為 0，即（0，0）是沒有意義的。

若兩個數的最大公因數為1，我們稱這兩個數為互質數，或稱這兩個數互質（或互素）。

在此，我們重復兩個結論：

（1）a，b的最大公因數是最小的形如ma+nb的正整數。

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

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

2.最小公倍數

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

有一個結論：a，b的任意公倍數都是其最小公倍數的倍數。比如15和10的最小公倍數是30，那么15和10的任何公倍數都應該是30的倍數。這一點不難檢驗。問題是如何在一般情況下證明這個結論？我們只需要證明a，b的任意正的公倍數都是其最小公倍數的倍數即可。為此，我們設m是a，b的最小公倍數而N是a，b的任意正的公倍數。我們要證明N是m的倍數。事實上，由于m是a，b的最小公倍數而N是a，b的正的公倍數，因此，N不小于m，從而N-m應該為a，b的公倍數（一個數的兩個倍數之差仍為這個數的倍數）。且N-m不小于0。若考慮N-m，N-2m，N-3m…以上數列終于會從某一個開始小于0。

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

最小公倍數的求法可由下列結論轉化為最大公因數的求法。

兩個整數a，b的最小公倍數[a，b]和最大公因數（a，b）滿足[a，b]=（a，b）=a×b，即兩個數的最大公因數與最小公倍數的乘積等于這兩個數的乘積。

3.線性不定方程

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

事實上，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寫成形如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的一組整數解為

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

方程78x+30y=6即13x+5y=1。此時，13和5是互質的。按上面的方法，我們可以找到方程ax+by=1（a，b 互質）的一組解，若設是方程ax+by=1的一組解（通常叫特解），則該方程的所有解都可以表示成的形式，其中t取所有的整數（這種形式的解就叫通解）。

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

于是，求不定方程ax+by=1（a，b互質）整數解的問題就得到完全的解決。

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

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

于是，對于任意有整數解的不定方程，我們已經得到了求其所有整數解的方法。

在以上討論不定方程的過程中，我們先研究特殊情況，再設法把一般情況轉化為特殊情況。這是數學研究常用的方法，在小學數學教學中也應該適當地滲透這種方法。