APP下载

最大公因数与最小公倍数

2017-10-21张新春

湖南教育 2017年39期
关键词:公因数公倍数正整数

文︳张新春

最大公因数与最小公倍数

文︳张新春

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

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

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

猜你喜欢

公因数公倍数正整数
关于包含Euler函数φ(n)的一个方程的正整数解
小小数迷泽西之小房间里的大世界(下)
被k(2≤k≤16)整除的正整数的特征
《最大公因数》教案
周期数列中的常见结论及应用*
浅谈快速求最小公倍数法
浅谈快速求最小公倍数法
方程xy=yx+1的全部正整数解
《约分——最大公因数》教学设计
《约分
——最大公因数》教学设计