最大公约数和最小公倍数

最大公约数和最小公倍数学科：奥数教学内容：第5讲最大公约数与最小公倍数知识网络（1）整数a能被整数b（不为零）整除，数a就是数b的倍数，数b就是数a的约数。（2）几个数公有的约数，叫做这几个数的公约数，公约数的个数是有限的，其中最大的一个叫这几个数的最大公约数。若，，…，的最大公约数是d，则可记为（）=d（3）几个数公有的倍数，叫做这几个数的公倍数，公倍数可以有无限多个，但其中有一个最小，这个最小的就叫做这几个数的最小公倍数。若自然数的最小公倍数是m，则可记为［］=m（4）最大公约数的性质1）两个数的最大公约数的约数，都是这两个数的公约数，即：如果（a，b）=d，c|d，那么c|a，c|b。2）两个数分别除以它们的最大公约数，所得的商一定是互质的，即：如果（a，b）=d，那么（a÷d，b÷d）=1（5）最小公倍数的性质1）两个自然数的最大公约数与最小公倍数的乘积等于这两个数的乘积，即：若（a，b）=d，[a，b]=m，则dm=ab，且d|m2）若一个数c能同时被两个自然数a、b整除，那么c一定能被这两个数的最小公倍数整除。或者说，一些数的公倍数一定是这些数的最小公倍数的倍数。即：若[]=m，而，，…，，那么m|N。（6）以下两点需要特别注意：l）数a是数b的倍数，数b就是数a的约数，它们的最大公约数是b，最小公倍数是a。2）若两个数互质，则它们的最大公约数是1，最小公倍数是它们的积。（7）求最大公约数常用的方法有：列举法，分解质因数法，短除法，辗转相除法。（8）求最小公倍数常用的方法有：列举法，分解质因数法，短除法，最大公约数法。约数有：1、30，2、15，3、10，且每对中两个约数的积就是自然数本身。（4）对一个完全平方数来说，例如，由于它是6的平方，所以它有一个约数正好是6，与之配对的约数仍是6，其余的约数配对后，每组中有一个小于6的约数，另一个是大于6的约数。（5）非完全平方数的约数是偶数个，完全平方数的约数是奇数个。（6）有关最大公约数与最小公倍数的问题，其叙述方式是多种多样的，在解题时一定要认真审题，不能简单地在题中看到“最多”就认为是求最大公约数，看到“最少”就认为是求最小公倍数。（7）解答问题一般都有多种解法，请同学们一定选择快捷简便而又适合自己思路的方法。（8）为了更好地解决有关最大公约数、最小公倍数的问题，还必须掌握有关整除的知识。经典例题［例1］已知两个自然数的和是60，它们的最大公约数与最小公倍数之和是84，求这两个自然数各是多少？解答不妨设这两个自然数为a、b，若（a，b）=m，则，且（）=1。由题意可知a+b=60，即所以。又因为，故得知m为60、84的约数。而（60，84）=12，所以m只可取l、2、3、4、6、12六种可能值，但当m取1、2、3、4、5、6时均不能满足和。所以m仅能取12，则=60÷12=5若、分别取2、3时，则相对应的a、b值为24和36。答：这两个自然数为24和36。[例2]求180、840、300的最大公约数。解答☆解法一：根据最大公约数的定义，把三个数分别分解质因数，取出全部公共的质因数，每个公共的质因数取出现的最低次数，把这些公共质因数的乘方相乘即得最大公约数。把180、840、300分解质因数：，，取各公共质因数2、3、5出现的最低次数，则180、840、300的最大公约数为。☆解法二：短除法。用三个数的大于1的公约数作除数，除到最后三个商互质为止，各除数相乘之积就是要求的最大公约数。180、840与300的最大公约数为2×2×3×5=60。［例3］求68、72、84的最小公倍数。解答☆解法一：根据最小公倍数的定义，把三个数分别分解质因数，取出全部质因数，且各质因数取出现的最高次数，然后相乘即得最小公倍数。把68、72、84分解质因数：取全部质因数2、3、7、17出现的最高次数，便得68、72、84的最小公倍数为☆解法二：应用短除法，先用三个数的大于1的公约数去除，除到三个商互质时，再用两个数的大于1的公约数去除，除到三个商两两互质时为止，最后把所有除数及最末的三个商相乘就得到要求的最小公倍数。68、72与84的最小倍数为2×2×3×17×6×7=8568［例4］求1903与2249的最大公约数。思路剖析不容易直接看出1903与2249的大于1的公约数，所以可先求2249除以1903的余数r，所以（2249，1903）=（1903，r）；如果1903不是r的倍数，再对1903与r做除法，然后把求1903与r的最大公约数转化为求更小的一对数的最大公约数，这样反复做，直到能求出最后一对数的最大公约数，它也就是1903与2249的最大公约数。解答因为2249÷1903=l……346，所以（2249，1903）=（1903，346）（1）又因为1903÷346＝5……173，所以（1903，346）=（346，173）（2）由于346÷173＝2，即346是173的倍数，所以（346，173）＝173（3）根据（1）、（2）、（3）三式可以得到（2249，1903）=（1903，346）=（346，173）=173点津这种通过反复作除法来求最大公约数的方法叫做辗转相除法。在以后的实际计算中，可采用如下的简写格式：简写格式的步骤为：第一步，把两数写在三条竖线之间；第二步，较大数除以较小数，商写在与较小数相邻那条竖线的外边，商与除数的积写在较大数的下边，求余数；第三步，如果第二步求出的余数不等于0，就重复第二步的计算，直到余数是0为止；第四步，最后一个非零余数就是原来两数的最大公约数。［例5］有任意50个自然数，从中是否可以取出若干个（一个或多个）数，使得取出的这些数之和恰好是50的倍数？说明理由。思路剖析50个数太多，我们先从较少的数开始考虑，以便发现问题的本质。如果是两个数a、b，那么从中取数有两种情形：取一个数，取两个数作和。我们考虑a与a+b；如果a能被2整除，那么取a就符合要求；如果a+b能被2整除，那么a与b就符合要求；如果a与a+b都不能被2整除，说明a与a+b都是奇数，于是a+b与a的差是偶数，即b是偶数，取b就符合要求。总之，对两个数的情形，结论成立。如果是三个数a、b、c，那么从中取数有三种情形：取一个数，取两个数作和，取三个数作和。我们考虑a、a+b、a+b+c；如果a能被3整除，那么取a就符合要求；如果a+b能被3整除，那么取a与b就符合要求；如果a+b+c能被3整除，那么取a、b、c就符合要求；如果a、a+b、a+b+c都不能被3整除，则它们除以3所得的余数只能是1或2，因而必有两个余数相等，这时余数相等的两数之差可被3整除，因而仍可取到符合要求的数。总之，对三个数的情形，结论也成立。对多于三个数的情形，可以类似考虑，所以问题能够解决。解答把原来的50个数分别记为、、、…、、考虑，其中可以看出、、、…、、，以及它们中间任意两个的差（大减小），都是原来50个数中几个数的和。若、、、…、、中有一个是50的倍数，则取这个数就符合要求。若、、、…、、中每个数除以50所得余数都不等于0，那么它们分别除以50所得的余数只能是1、2、3、4、…、48、49中的一个，所以至少有两个数，它们被50整除，说明仍可取得符合要求的数。总结以上可知，在50个数、、、…、、中可以找到若干个数，它们的和能被50整除。［例6］在一个30×24的方格纸上画一条对角线（见图1），这条对角线除两个端点外，共经过多少个格点（横线与竖线的交叉点）？思路剖析（30，24）=6，说明如果将方格纸横、竖都分成6份，即分成6×6个相同的矩形，那么每个矩形是由（30÷6）×（24÷6）=5×4（个）小方格组成。在6×6的简化图中，对角线也是它所经过的每一个矩形的对角线，所以经过5个格点（见图2）。在对角线所经过的每一个矩形的5×4个小方格中，对角线不经过任何格点（见图3）。解答对角线共经过格点（30－24）－l=5（个）［例7］一张长方形纸，长2703厘米，宽1113厘米。要把它裁成若干个同样大小的正方形，纸张不能有剩余且正方形的边长要尽可能大。问：这样的正方形的边长是多少厘米？思路剖析由题意可知，正方形的边长即是2703和1113的最大公约数。在学校，我们已经学过用短除法求两个数的最大公约数，但有时会遇到类似此题情况，两个数除了1以外的公约数一下不好找到，但又不能轻易断定它们是互质数，怎么办？在此，我们以例7为例介绍另一种求最大公约数的方法。对于本题，可做如图4的图解。从图4中可知；在长2703厘米、宽1113厘米的长方形纸的一端，依次裁去以宽（1113厘米）为边长的正方形2个。在裁后剩下的长1113厘米、宽477厘米的长方形中，再裁去以宽（477厘米）为边长的正方形2个。然后又在裁剩下的长方形（长477厘米，宽159厘米）中，以159厘米为边长裁正方形，恰好裁成3个，且无剩余。因此可知，159厘米是477厘米、1113厘米和2703厘米的约数。所以裁成同样大的，且边长尽可能长的正方形的边长应是159厘米。所以，159厘米是2703和1113的最大公约数。解答让我们把上述图解过程转化为计算过程，即：2703÷1113，商2余4771113÷477，商2余159477÷159，商3余0或者写为2703=2×1113+4771113=2×477+159477=3×159当余数为0时，最后一个算式中的除数159就是原来两个数2703和1113的最大公约数。可见，477=159×3，1113=159×3×2+159=159×7，2703=159×7×2+477=159×7×2+159×3=159×7又因为7和17是互质数，所以159是2703和1113的最大众约数。答：正方形的边长是159厘米。［例8］在一间屋子里有100盏电灯，排成一行，依从左至右的顺序，编上号码1、2、3、4、…、99、100，每盏灯上有一个拉线开关。开始时，全部的灯都关着，有100个同学在门外排着队，第1个同学进屋把编号是1的倍数的所有电灯开关都拉一下即把所有电灯开关都打开了）；接着第二个同学进屋把编号是2的倍数的所有电灯开关都拉一下（即把所有编号为偶数的电灯又关上了），第3个同学进屋把所有编号是3的倍数的电灯开关都拉一下，如此下去，直到第100个同学进屋把第100号电灯开关拉了一下，这样做完以后，问哪些电灯还是亮着的？思路剖析这道题题目很长，看完后觉得很难下手。我们来分析一下：电灯如果最后是亮的，那么它一定要被拉奇数次；因为一开一关拉两次是一个周期，拉偶数次的电灯最后一定是关着的。例如，一盏电灯被拉了4次，在经历开→关→开→关之后一定是关着的。那么哪些电灯被拉奇数次呢？这取决于它的编号。例如，第30号，它是1、2、3、5、6、10、15、30的倍数，因此第l、2、3、5、6、10、15、30个同学进屋时都会拉第30个电灯，即拉8次，因此它最后是关着的。这里不难发现，看一个编号是哪些数的倍数，其实就是找这个数有哪些约数，约数的个数就代表了电灯被拉的次数，所以，我们只要找出约数个数是奇数的编号就可以知道哪几盏灯是亮的。自然数中只有完全平方数的约数个数是奇数，100以内的完全平方数有l、4、9、16、25、36、49、64、81、100，所以编号是这些数的电灯最后是亮着的。解答由上述分析可知编号是l、4、9、16、25、36、49、64、81、100的电灯最后是亮的。［例9］把1、2、3、4、5、6、7、8、9这九个数，按照不同的次序排列，可以得到许多不同的九位数，如345219876等等。求所有这些九位数的最大公约数是多少？思路剖析一个数，如果各数位上的数字之和能被9整除，那么这个数一定能被9整除，这是能被9整除的数的特征。组成的这许多个九位数虽然各不相同，但它们都是由1~9这九个数字按不同的次序排列得到的，每个九位数的各数位之和都是1+2+3+…+9=45=9×5，所以每个九位数都是9的倍数，因而9是这些九位数的公约数。下面的问题就是研究9是不是这些九位数的最大公约数。现在任取一个九位数，如123456789，令12356789=9×a，则比它大9的九位数是123456798=9×（a+1），因为a与（a+l）互质，所以这两个数没有比9更大的公约数了，这说明，所有这些九位数的最大公约数是9。解答由上述分析可知，所有这些九位数的最大公约数是9。［例10］A、B两个数都恰恰只含有质因数3和5，它们的最大公约数是75，已知A有12个约数，B有10个约数，那么A、B两数的和等于多少？思路剖析要求A、B两数的和是多少，最好能先求出A、B的值各为多少，题目只是告诉我们A、B两数只含有质因数3、5，且它们的最大公约数为75，即A、B两数都含有这个数，且共同的只有这个数，因A有12个约数，12=2×6或=3×4，B有10个约数，10＝2×5。若12＝2×6则它们的共同因数为，与题目相矛盾，舍去，所以12取3×4＝（2+l）×（3+l），对于B这个数只能取，所以A中5的指数不能变，所以。解答10=2×5，12=2×6（舍去）=3×4=（2+1）×（3+l），所以、答：A、B两数的和等于2550。［例11］某厂加工一批零件，每个零件需要一个螺栓，三个螺母，七个螺钉，已知每个工人每小时可完成3个螺栓或12个螺母或18个螺钉，要想能均衡生产，使每件零件都配上套，生产这三种零件各需安排多少人？思路剖析因为这种零件中所需的螺母是螺栓的3倍，螺钉是螺栓的7倍，所以我们只需先求生产一个螺栓、一个螺母、一个螺钉配套起来各需的人数，再用生产螺母的人数扩大3倍，生产螺钉的人数扩大7倍便可以达到题目要求了。要想顺利进行，必须每小时加工各种零件的个数是3、12、18的公倍数，所以我们可以先求它们的公倍数，再求各种零件所需人数。解答因为［3，12，18］=3636÷3=12（人）36÷12×3=9（人）36÷18×7=14（人）答：生产螺栓的需12人，生产螺母的需9人，生产螺钉的需14人。发散思维训练l．老虎和豹进行跳跃比赛；老虎每次跳米，豹每次跳米，它们每秒都又跳一次。比赛途中，从起点开始，每隔米设有一个陷阱。它们之中谁先掉进陷阱？一个掉进陷阱时另一个跳了多远？2．已知两个自然数的和为54，它们的最小公倍数与最大公约数的差为114，求这两个自然数。3．有甲、乙、丙三种溶液，分别重千克、千克和千克。现要将它们全部分别装入小瓶中，每个小瓶装入液体的重量相同。问：每瓶最多装多少千克？4．甲校和乙校有同样多的同学参加数学竞赛，学校用汽车把学生送往考场。甲校用的汽车，每车坐15人，乙校用的汽车，每车坐13人，结果甲校比乙校少派一辆汽车。后来每校各增加一个人参加竞赛，这样两校需要的汽车就一样多了。最后又决定每校再各增加一个人参加竞赛，乙校又要比甲校多派一辆汽车。问最后两校共有多少人参加竞赛？5．大雪后的一天，小飞和爷爷共同步测一个圆形花圃的周长，他俩的起点和走的方向完全相同，小飞每步长48厘米，爷爷每步长72厘米，由于两人脚印有重合，所以各走完一圈后雪地上只留下40个脚印，求花圃的周长？6．甲数有9个约数，乙数有10个约数，甲、乙两数的最小公倍数是2800，求甲、乙两数各是多少？7．一对啮合齿轮，一个有132个齿，一个有48个齿，其中啮合的任意一对齿从第一次相接到再次相接，两个齿轮各要转动多少圈？8．有两个油桶，一个容量为27升，另一个容量为15升，只利用这两个油桶怎样从一个大油桶中倒出6升油来。发散思维训练1．解：老虎掉进陷阱时与起点的距离应是和的最小整数倍，即和的最小公倍数。（米）所以老虎掉进陷阱时跳了（次）同理，豹掉进陷阱时与起点的距离为（米）所以豹掉进陷阱时跳了（次）所以豹先掉进陷阱，它掉进陷阱时，老虎跳了（米）2．解：设这两个自然数分别为a与b，a＜b，（a，b）=da=，，其中。因为a+b=54，所以于是有，因此d是54的约数。又因为这两个数的最小公倍数与最大公约数的差为114。所以于是有因此，d是114的约数故d为54与114的约数由于（54，114）=6，6的约数有：1、2、3、6，所以d可能取1、2、3、6这四个值。如果d=l，由，有；又由，有。115=1×115=5×23，但是1+115=116≠54，5+23=28≠54，所以d≠1。如果d=2，由，有；又由，有。58=1×58=2×29，但是1+58=59≠27，2+29=31≠27，所以d≠2。如果d=3，由，有；又由，有。39=l×39=3×13，但是1+39=40≠18，3+13=16≠18，所以d≠3。如果d=6，由，有；又由，有。20表示成两个互质数的乘积有两种形式：20=l×20=4×5，虽然1+20=21≠9，但是有4+5=9，所以取d=6是合适的，并有，。故a=6×4=24，b=6×5=30。答：这两个自然数为24和30。3．解：如果三种溶液的重量都是整数，那么每瓶装的重量就是三种溶液重量的最大公约数。现在的问题是三种溶液的重量不是整数。要解决这个问题，可以将重量分别乘以某个数，将分数化为整数，求出数值后，再除以这个数。为此，先求几个分母的最小公倍数，［6，4，9］=36，三种溶液的重量都乘以36后，变为150、135和80。（150，135，80）=5上式说明，若三种溶液分别重150千克、135千克、80千克，则每瓶最多装5千克。可实际重量是150、135、80的，所以每瓶最多装（千克）答：每瓶最多装千克。4．解：原来甲校比乙校少派一辆汽车，各增加一人以后，两校需要的汽车就一样多了，这说明甲校在没有增加这一人以前恰好坐满了所派的全部汽车（增加的一辆汽车就坐增加的这一人），所以甲校原来参加竞赛的人数是15的倍数。后来又各增加一个人，乙校又要多派一辆汽车，这说明在第=次增加人数之前，乙校所派的车恰好坐满，也就是说，乙校这时的人数是13的倍数，即一个15的倍数加1以后是13的倍数。由此可知，甲乙两校各增加一人后，派车的辆数相等，但甲校有一辆车只坐一个人，而乙校每车13人恰好坐满原来所派的车。可以设想，甲校原来所派的车每车下来两个人坐到增加的这辆车上去，就会正好跟乙校的情况一样了，即刚好坐满增加的这辆车。因此，原来甲校的车辆数是：（l3－1）÷（l5－13）=6（辆），原来每校参赛人数是15×6=90（人）。答：最后甲乙两校共有184人参加竞赛。5．解：要想求出花圃的周长，只要求出小飞和爷爷一圈留下多少个脚印就行了，由于小飞和爷爷测时起点和方向完全相同。且两人脚印有重合，这说明，他俩从起点出发到第一次脚印重合时所走过的路程是相同的，这个路程是小飞和爷爷步长的倍数。即：［72，