最大公因数与最小公倍数

文︳张新春

最大公因数与最小公倍数

文︳张新春

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的最大公因数去除这个方程的两边，即可把这个方程转化为上述研究过的方程。

于是，对于任意有整数解的不定方程，我们已经得到了求其所有整数解的方法。

在以上讨论不定方程的过程中，我们先研究特殊情况，再设法把一般情况转化为特殊情况。这是数学研究常用的方法，在小学数学教学中也应该适当地渗透这种方法。