七年级王牌竞赛 第十七讲 最大公约数与最小公倍数
巡山小妖精
640次浏览
2021年02月01日 08:08
最佳经验
本文由作者推荐
当那一天真的来临-读书郎歌词
第十七讲
最大公约数与最小公倍数
….
【趣题引路】
如图，一个圆圈上有
n
(
n
<10 0)
个孔．小明像玩跳棋一样，从
A
孔出发，逆时针方向将一枚棋子跳动，
每 步跨过若干个孔，希望跳一圈后回到
A
孔．他先每步跳过
2
个孔，结果只能跳 到
B
孔；他又试着每步跳
过
4
个孔，结果还是跳到
B
孔；最后他每步跳过
6
孔，正好回到
A
孔．问这个圆圈上一共有多少个孔？
B
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
．因< br>n
<100
，故
n
只可能是
16
，
31，
46
，
61
，
76
，
91
，其中仅 有
91
是
7
的倍
数，故
n
=91
，即圆圈 上有
91
个孔．
【知识延伸】
1
．
（
1
）设
a
1
，
a
2
是两个整数 ，如果
d
|
a
1
，
d
|
a
2，那么
d
就称为
a
1
和
a
2
的公约数 ．一般地，设
a
1
，
……
a
k
是
k
个整数，如果
d
|
a
1
，
…
，
d
|
a
k
，那么
d
就称为
a
1
，
a
k
的公约数．
（
2
）设
a
1
，
a
2
，是两个不全为零的整数，那么
a
1
，
a< br>2
的公约数中最大的称为
a
1
和
a
2
的最大 公约数，
记作
(
a
1
，
a
2
)
．
一般地，
设
a
1
，
…
a
k
是k
个不全为零的整数，
那么
a
1
，
…
，
a
k
的公约数中最大的称为
a
1
，
…
a
k
．
的
最大公约数，记作
(
a
1
，
…，
a
k
).
a
1
，
…
，
a
k
的公约数一定是最大公约数的约数．
2
．设
a
1
，
a
2
是两个均不等于零的整数，如果
a
1
|< br>l
，
a
2
|
l
，则称
l
是
a
1
，
a
2
的公倍数，
a
1
，
a
2
，的正的公
倍数中最小的称为
a
1
与
a
2
的最小公倍数，一般地，设
a
1
，
…
，
a
k
是
k
个均不等于零的整数
.
如果
a
1
|
l
，
…
，
a
k
|
l
，则称l
是
a
1
，
…
，
a
k
！的公 倍数，其中正的公倍数中最小的称为
a
1
，
…
，
a
k
的最小公倍数，其他公倍
数一定是最小的公倍数的倍数．
3
．若将
a
，
b
进行质因数分解，并将它们表示成
a
m
a
2
，
a
p
1
a
1
p
2
...
p
m
2
b
p
1
1
p
2
...
p
m
m
其中
P
1
，
P
2
…
，
P
3
为质数：
α
1
，
α2
，
…
，
α
m
，
β
1
，β
2
，
…
，
β
m
．为非负整数，且设
t
i
、
s
i
分别为
α
i
、
βi
(
i
=1
，
2.…
，
m
)
中的较小者与较大者，则
t
t
t
（
a
，
b
）
=
p
1
，
p
2
...p
m
1
2
m
t
t
t
[
a，
b
]=
p
1
．
p
2< br>...
p
m
1
2
m
4
．最大公约数与最小公 倍数的重要性质
（
1
）如果
b
|
a
，则 （
a
，
b
）
=
b
，
【
a
，
b
】
=
a
．
（
2
）对于任意 的正整数
m
，有（
am
，
bm
）
=
m(
a
，
b
)
，
[
am
，
bm
]=
m
[
a
，
b
]
．
（
3
）若
a=bq+r
(
a
>
b
，0≤
r
<
b
)
，则有
(
a
，
b
)=(
b
，
r
)
．
这一性质表示求（
a
，
b
）可转化为求（
b
，
r
）
．由于
b
和
r
相对于
a
与
b
来说要小，求 （
b
，
r
）应较求
（
a
，
b
）简 便
.
若
b
和
r
仍比较大，可重复使用这一性质
.< br>这种方法称之为辗转相除法．
（
4
）
(
a
1
，
a
2
，
a
3
)=((
a
1< br>，
a
2
)
，
a
3
)
．
< br>（
5
）
ab
=(
a
，
b
)·
[
a
，
b
]
．
5
．若
(< br>a
1
，
a
2
)=1
，则称
a
1与
a
2
互质．若
(
a
1
…
，
a
k
)=1
，则称
a
1
，
…
，
a
k
互质．
值得注意的是
k
个数互质，不一定两两互质，如 （
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
）若（< br>a
，
b
）
=1
，则（
ac
，
b）
=
（
c
，
b
）
；
（5
）若（
a
，
b
）
=1
，
c
|
a
，则（
c
，
b
）
=1
．
例
1
（
2002
年黄冈市初中竞赛题）
23
个不 同的正整数的和是
4845
，试问：这
23
个数的最大公约数可
能达 到的最大的值是多少？写出你的结论，并说明理由．
【解析】
设这
23个彼此不同的正整数为
a
1
，
a
2
，
…
，
a
23
，
并且它们的最大公约数是
d
，
则a
1
=
db
1
，
a
2
=
db
2
…
，
a
23
=
db
23
，依题 意，有
4845=
a
1
+
a
2
+…+< br>a
23
=
d
(
b
1
+
b
2
+…+
b
23
)
．
∵
b
1< br>，
b
2
…
，
b
23
也是彼此不等的正整数，
∴
b
1
+
b
2
+…+
b
23
≥1+2+·…+23=276.
因此，
4845=
d(
b
1
+
b
2
+…+
b
22
+
b
23
)
≥276
d
，
∴
d
4845
51
17
2 76
92
又因为
4845=19×
17×
15
，因此，d
的最大值可能是
17
．
当
a
1
= 17
，
a
2
=17×
2
，
a
3
= 17×3…
，
a
22
=17×
22
，
a
2 3
=17×
23
时，得
a
1
+
a
2
+…+
a
22
+
a
23
=17(
1+2+…+22
)+17×
23
=17×
253+17×
23=17×
285=4845
本题的解 题思路是：可设这
23
个不同的正整数为
a
1
，
a
2
，
…
，
a
23
，且
a
1
=db
1
，
a
2
=
db
2
，
…
，
a
23
=
db
23
，
则
484 5=
d
(
b
1
+
b
2
+
…+b
23
)
．
要使
d
最大，
则
b1
+
b
2
+…+
b
23
如最小．
故可 求出
d
的取值范围，
再根据
d
|4845
，
求出< br>d
的值．
例
2
求
1008
和
270
的最大公约数与最小公倍数．
解析解法一：短除法
2
1008
3
504
3168
56
270
135
45
15
于是，< br>(1008
，
270)=2×
3×
3=18
，
【
1008
，
270
】
=2×
3×
3×
56×
15=15120
．
解法二：利用因数分解法
1008=24×
32×
7=24×
32×
50×
71
，< br>
270=2×3
×5
=2×3
×5
×7
，于是，（
1008
，
270
）=2×3
=18.
[100 8
，
270]=2
×3
×5×7=1
5120.
解法三：辗转相除法
1008=270×3+198
270=198×1+72，
198=72×2+54，
72=54×1+18，
54=18×3.
为了书写便利，上述过程可采用以下形式：
100
8
810
198
144
54
54
0
也可更简洁地写成以下形式：
（
1008
，
270
）
=
（
198
，
270
）
=
（
198
，
72
）
=
（
54
，
7 2
）
=
（
54
，
18
）
=18
，
[1008
，
270]=
18
72
54
18
3
2
270
198
3 4
3
3
1
0
1
0
2
1008
270
=15120.
18
点评：短除法实行的过程，实际上就 是不断地提取公因数的过程，直至（
56
，
15
）
=1
为止
.
例
3
（
2001
年希望杯初一数学竟赛试题） 古人用天干和地支记次序，其中天干有
10
个：甲、乙、丙、
丁、戊、己、庚、辛、王 、癸，地支有
12
个：子、丑、寅、卵、辰、已、午、未、申、酉、戌、亥
.
将天
干的
10
个汉字和地支的
12
个汉字分别循环排列成如下两行：
甲乙丙丁戊已庚辛王癸甲乙丙丁戊己庚辛壬癸……
子丑寅卵辰已午未申西成亥子丑寅卵辰已午未申西戌亥……
从左向右数，第
1
列是甲子，第
2
列是乙丑，第
3
列是丙寅……则当第
2< br>次甲和子在同一列时，该列
的序号是（
）
A.31 B.61 C.91 D.121
解析
“甲”在第 一行出现的位置是
10m+1
，
m=0
，
1
，
2… ，
“子”在第二行出现的位置是
12n+1
，
n=0
，
1< br>，2….
∴“甲”和“子”在同一列时应有
10m+1=12n+1
即
10m=12n
当
m=n=0
时是第一次“甲”“子”同列，第二次“甲”“子”同列时应是使得
10m=12n
成立的最小正
整数
m
和
n
，即
m=6
，< br>n=5.
∴应是第
61
号位置
.
故选
B.
点评：“甲”“子”在同一列时，它们的序号相同，这是解题的关键
.
例
4
（
1999
年“希望杯”初一数学竞赛试题）已知一组两两不等的四位数，它们的最大 公约数是
42
，
最小公倍数是
90090.
问这组四位数最多能有多 少个？它们的和是多少？
解析
设这组四位数共
n
个， 分别为
a
1
=42x
1
，
a
2
=42x< br>2
.…，
a
n
=42x
n
，其中的每个
a< br>i
=42x
i
是四位数，所
以
1000≤42x
i
<10000
23
100 0
10000
x
i
239
.
42
42
由题设知
90090=[a
1
，< br>a
2
…，
a
n
]
=[42x
1< br>，
42x
2
,
…，
42x
n
]
< br>=42[x1
，
x
2
,
…，
x
n
]
，
所以，
[x1
，
x
2
,
…，
x
n
]=
90090
=2145=3×5×11×13，其中
23
<239.
①
42
可知
xi
是由
3
，
5
，
11
，
13
每个至多用一次组合成的在
23
和
239
之间的自然数，并且两两不同
.
其中两
个质因数组合且满足①式者，只有
33
，
39
，
55
，
65
，
143
，三个质因数组合且满足①式者，有< br>165
和
195
，
一个质因数以及多于三个质因数的积，都不能满足① 式，因此，最多产生
7
个两两不同的四位数
.
a
1
=42×33=1386，
a
2
=42×39=1638，
a
3
=42×55=2310，
a
4
=42×65=2730，
a
5
=42×143=6006，
a
6
=42×165=6930，
a
7
=42×195=8190.