初中数学培优竞赛讲座第32讲--最大公约数与最小公倍数

1第三十二讲最大公约数与最小公倍数如图，一个圆圈上有n(n＜100＝个孔．小明像玩跳棋一样，从A孔出发，逆时针方向将一枚棋子跳动，每步跨过若干个孔，希望跳一圈后回到A孔．他先每步跳过2个孔，结果只能跳到B孔；他又试着每步跳过4个孔，结果还是跳到B；最后他每步跳过6孔，正好回到A孔．问这个圆圈上一共有多少个孔?思路点拨依题意，每步跳过2孔，连起点一共要跳过3个孔，故除掉B孔外，圆圈上的孔数是3的倍数，有3│n—1；每步跳过4个孔，连起点一步要跳过5个孔，故除掉B孔外，圆圈上的孔数是5的倍数，因此，有5│n—1；又每步跳过6个孔时，可回到A孔，这表明7│n．因(3，5)=1，故15│n—1．因n100，故n只可能是16，31，46，61，76，91，其中仅有91是7的倍数，故n=91，即圆圈上有91个孔．知识要点：1．(1)设a1，a2是两个整数，如果d│a1，，d│a2，那么d就称为a1和a2的公约数．一般地，设kaaa、、、21是k个整数．如果d│a1，…d│ak，那么d就称为kaaa、、、21的公约数．(2)设a1，a2是两个不全为零的整数，那么的公约数中最大的称为a1和a2的最大公约数，记作(a1，a2)．一般地，设kaaa、、、21是k个不全为零的整数，那么kaaa、、、21的公约数中最大的称为kaaa、、、21的最大公约数，记作(a1，a2，…，ak)．kaaa、、、21的公约数一定是最大公约数的约数．2．设a1，a2是两个均不等于零的整数，如果a1│l，a2│l，则称l是a1，a2的公倍数，a1，a2的正的公倍数中最小的称为a1与a2的最小公倍数．一般地，设kaaa、、、21是k个均不等于零的整数．如果a1│l，…，ak│l，则称l是kaaa、、、21的公倍数，其中正的公倍数中最小的称为kaaa、、、21的最小公倍数，其他公倍数一定是最小的公倍数的倍数．3．若将a，b进行质因数分解，并将它们表示成mmpppa2121，mmpppb2121．其中p1，p2，…，Pm为质数，α1，α2，，…αm，β1，β2，…，βm为非负整数，且设ti、ts分别为αi、βi(I=1，2，…，m)中的较小者与较大者，则(a，b)=mtmttppp2121，[a，b]=msmssppp2121．4．最大公约数与最小公倍数的重要性质(1)r如果b│a，则(a，b)=b，[a，b]=a．(2)对于任意的正整数m，有(am，bm)=m(a，b)，[am，bm]=m[a，b]．(3)若a=bg+r(a＞b，0≤r＜b＝，则有(a，b)=(b，r)．这一性质表示求(a，b)可转化为求(b，r)．由于b和r相对于a与b来说要小，求(b，r)应较求(a，b)简便．若b和r仍比较大，可重复使用这一性质．这种方法称之为辗转相除法．(4)(a1，a2，a3)=((al，a2)，a3)．(5)ab=(a，b)×[a，b]．25．若(a1，a2)=1，则称a1与a2互质．若(a1，…，ak)=1，则称a1，…，ak互质．值得注意的是居个数互质，不一定两两互质，如(6，9，10)=1，而(6，9)=3．6．(1)若(a，b)=1，则(a，a±b)=1，(a±b，b)=1，(a±b，ab)=1(2)若(a，b)=1，a│bc，则a│c．(3)若(a，b)=1，a│c，b│c，则ab│c；(4)若(a，b)=1，则(ac，b)=(c，b)；(5)若(a，b)=1，c│a，则(c，b)=1．【例1】(黄冈市初中竞赛题)23个不同的正整数的和是4845，试问：这23个数的最大公约数可能达到的最大的值是多少?写出你的结论，并说明理由．思路点拨设这23个彼此不同的正整数为a1，a2…，a23，并且它们的最大公约数是d，则a1=db1，a2=db2，…，，a23=db23，依题意，有4845=a1+a2+…+a23=d(b1+b2+…+b23)．∵b1，b2，…，b23也是彼此不等的正整数，∴b1+b2+…+b23≥1+2+…+23=276．因此，4845=d(b1+b2+…+b23)≥276d，∴d≤9251172764845．又因为4845=19×17×15，因此d的最大值可能是17．当a1=17，a2=17×2，a3=17×3，…，a22=17×22，a23=17×32时，得a1+a2+…+a23=17(1+2+…+22)十17×32=4845．注本题的解题思路是：可设这23个不同的正整数为a1，a2…，a23，且a1=db1，a2=db2，…，，a23=db2，则4845=d(b1+b2+…+b23)．要使d最大，则b1+b2+…+b23应最小．故可求出d的取值范围，再根据d│14845，求出d的值．【例2】(希望杯初一数学竞赛试题)古人用天干和地支记次序，其中天干有10个：甲、乙、丙、丁、戊、己、庚、辛、壬、癸，地支有12个：子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥．将天干的10个汉字和地支的12个汉字分别循环排列成如下两行：甲乙丙丁戊己庚辛壬癸甲乙丙丁戊己庚辛壬癸…子丑寅卯辰巳午未申酉戌女子丑寅卯辰巳午未申酉戌亥……从左向右数，第1列是甲子，第2列是乙丑，，第3列是丙寅……则当第2次甲和子在同一列时，该列的序号是()A．31B．6lC．91D．121思路点拨“甲”在第一行出现的位置是l0m+1，m=0，1，2，…，“子”在第二行出现的位置是12n+1，n=0，1，2，…．∴“甲”和“子”在同一列时应有l0m十1=12n十l即l0m=12n当m=n=0时是第一次“甲”“子”同列，第二次“甲”“子”同列时应是使得l0m=12n成立的最小正整数m和n，即m=6，n=5．∴应是第61号位置．故选B．注：“甲”“于”在同一列时，它们的序号相同，这是解题的关键．【例3】(北京市竞赛)张华、李亮、王民三位同学分别发出新年贺卡x、y、z张．如果已知x，y，z的最小公倍数为60，x和y的最大公约数为4，y和z的最大公约数为3，那么张华发出的新年贺卡是多少张?思路点拨由题意可知，y不仅是3的倍数，而且是4的倍数，即y是12的倍数．同时y是60的约数，故而可求y．∵(x，y)=4，(y，z)=3，∴y是3与4的倍数，而3与4互质，故y是12的倍数．又∵[x，y，z]=60，∴y=12，60．进而可求出x．∵[x，y，z]=60=3×4×5．当y=12时，x、z中至少有一个含有因数5．若x中有因数5，又x中有因数4，且4与5互质，∴x中有因数20．而[x，y，z]=60，(x，y)=4，故x==20．3当x中没有因数5，∵x中有因数4，且x是60的约数，∴x=4，或x=12，而(x，y)=4，故x=4．当y=60时，(x，y)=4，而x中没有因数5，且[x，y，z]=60=3×4×5，故x=4．因此，张华发出的贺年卡为4张或20张．注(1)本题的切入点是最大公约数和最小公倍数；(2)注意答案的两种可能性．【例4】在一间屋子里有100盏电灯排成一横行，依从左到右的顺序编上号码1，2，3，…，100．每盏电灯上有一根拉线开关，最初所有电灯全是关的，现有100个学生在门外排着队，第一个学生走进屋来，把编号是1的倍数的电灯的开关拉一下；接着第二个学生走进屋来，把凡是编号是2的倍数的电灯开关拉了一下；…；最后第100个学生走进屋来，把编号是100的倍数的电灯的开关拉了一下，这样做过以后，问哪些电灯是亮的?思路点拨由于最初所有电灯是关着的，所以只有那些拉了奇数次开关的电灯才是亮的，而每一盏电灯的拉线开关被拉了多少次取决于这盏灯的编号的数字有多少个不同的正约数，最后亮着的灯的编号只有为完全平方数．所以，只有编号为1，4，9，16，25，36，49，64，81，100的电灯最后是亮着的．注：本题的一个重要条件是最初时灯都是关着的．然后对每个编号分解质因数．【例5】两个正整数的和是60，它们的最小公倍数是273，则它们的乘积是()A．273B．819C．1911R3549思路点拨设两个正整数为a与b，则a+b=60=22×3×5，[a，b]=273=3×7×13．显然，a，b的最大公约数是1或3．如果(a，b)=1，则[a，b]=a×b．a、b只能取21、13，7、39，1、273，3、91，其和均不为60．因此，(a，b)=3，于是a=3×7，b=3×13，∴a×b=(3×7)×(3X×3)=819．故选B．注：本题的精妙之处在于由a+b和[a，b]的两个质因式的分解，确定出a和b的最大公为数是1或3．【例6】用整元的人民币购物，若用多于7元的任意元钱去买单价为3元和5元的两种雪糕，一定可以把钱花完，请证明这一结论．思路点拨用任意元钱n(n＞7)去买单价为3元的雪糕，只能余l元或2元．若余2元时，少买一根3元雪糕，余数就为2+3=5元，恰能买一块5元的雪糕．若余1元时，少买3根3元的雪糕，余数为1+3×3=10元，恰能买2根5元雪糕．若n能被3整除，就用所有钱去买3元的雪糕，恰合题意．注：由3的同余数入手分类，结合拼凑法使问题得到证明．【例7】已知两数和是60，它们的最大公约数与最小公倍数之和是84，求此二数．思路点拨设所求二数为x，y，且(x，y)=d，令x=ad，y=bd，则(a，b)=1．根据题意有dabdba84160，由于(60，84)=12，所以d=l，2，3，4，6，12．而当d：1，2，3，4，6时，方程组无解．当d=12时，方程组变为65abba，解之得32ba或23ba佐：：．，故所求的两数为x=24，y=36．【例8】(“五羊杯’’竞赛题)设a与b是正整数，且a+b=33，最小公倍数[a，b]=90，则最大公约数(a，b)=()A．1B．3C．11D．9思路点拨令(a，b)=x，则x是a，b，a+b及[a，b]的公约数，故x是33和90的公约数，知x=1或4x=3．当x=1时，a与b互质，而a+b=33，当a不能被3整除，则b不能被3整除，而[a，b]=90，说明a、b至少有一个能被3整除．当b能被3整除，由a+b=33，则b也能被3整除，故(a，b)≠1，即x≠1．当x=3时，即有(a，b)=3，∴ab=[a，b]，(a，b)=3×90=32×5×6，而a+b=33，∴a=15，b=18，(a，b)=3．故选B．学力训练(A级)1．(“希望杯”培训题)2001的正约数的个数是()A．3B．4C．6D．82．(‘希望杯”竞赛题)下面的四句话中正确的是()A．正整数a和b的最大公约数大于等于aB．正整数a和b的最小公倍数大于等于abC正整数a和b的最大公约数小于等于aD．正整数a和b的公倍数大于等于ab3．360×473和172×361这两个积的最大公约数是()A．43B．86C．172D．44．(北京市竞赛题)a，b是彼此不相等的非零数字，则ababab与4017的最大公约数是．5．(上海市竞赛题)写出一组4个连续自然数，使它们从小到大顺次是5的倍数、7的倍数、9的倍数、11的倍数，这组自然数依次为．6．甲、乙、丙三人到李老师那里求学，甲每6天去一次，乙每8天去一次，丙每9天去一次，如果8月17日他们三人在李老师处见面，那么下一次在李老师处见面的时间是几月几日呢?(B级)1所有形如abcabc的六位数(a，b，c分别是0~9这十个数之一，可以相同，但a≠0)的最大公约数是()A．1001B．101C．13D．112用长为45cm，宽为30cm的一批砖，铺成一块正方形，至少需要()块．A．6B．8C．12D．163．祖孙两人的年龄都是合数，明年他们的岁数相乘是1610，那么祖孙两人今年的年龄分别是()A．70岁、23岁B．69岁、22岁C．115岁、14岁D．114岁、13岁4在正整数1，2，3，…，100中，能被2整除但不能被3整除的数的个数是()A．33B．34C．35D．375(2000年“希望杯”竞赛题)设m和n为大于0的整数，且3m+2n=225．(1)如果m