自然数的有关性质
剪枝的学问-
自然数的有关性质
一、知识要点
1
、最大公约数
定义
1
如果
a1,a2,
…
,an
和
d
都是正整数，
且
d
∣
a1, d
∣
a2,
…
,
d
∣
an
，那么
d
叫做
a1,a2,
…
,an
的公约数。公约数
中最大的叫做
a1,a2,
…
,an
的
最大公约数，
记作
(a1,a2,
…<
/p>
,an).
如对于
4
、
8
、
12
< br>这一组数，显然
1
、
2
、
4
都是它们的公约
数
，但
4
是这些公约数中最大的，所以
4
是它们的最大公约数，
记作
(4,8,
12)=4.
2
、最小公倍数
定义
2
如果
a1,a2,
…
,an
和
m
都是正整数，且
a1
∣
m, a2
∣
m
,
…
, an
∣
m
，那么
m
叫做
a1,a2,
…
,an
的公倍数。
公倍数中
最小的数叫做
a1,a2,
…
,an
的最小公倍数，
记作
[a1,a2,
…
,an].
< br>如对于
4
、
8
< br>、
12
这一组数，显然
24
、
48
、
96
都是它们的公
倍数，
但
24
是这些公倍数中最小的，
所以
24
是它们的最小公倍
数，记作
[4,
8,12]=24.
3
、最大公约数和最小公倍数的性质
性质
1
若<
/p>
a
∣
b,
则
(a,b)=a.
性质
2
若<
/p>
(a,b)=d,
且
n
< br>为正整数，则
(na,nb)=nd.
性质
3
若<
/p>
a
b
a
,
b
,
n
∣
a, n
∣
b,
则
n
n
n
.
性质
4
若
a=bq+r
(0
≤
r
则
(a,b)= (b,r) .
1
性质
4
实
质上是求最大公约数的一种方法，
这种方法叫
做辗转相除法。<
/p>
性质
5
若
b
∣
a,
则
[a
,b]=a.
性质
6
若
[a,b]=m,
且
n
为正
整数，则
[na,nb]=nm.
性质
7
若
a
b
a
,
b
,
n
∣
a, n
∣
b,
则
n
n
n
.
4
、数的整除性
定义
3
对于
整数
a
和不为零的整数
b
，如果存在整数
q
，
使得<
/p>
a=bq
成立，则就称
b
整除
a
或
a
被
b
整除，记作
b
∣
a
，若
b
∣
a
，我们也称
a
是
b
倍数；若
b
不能整除
a
，记作
b
a
5
、数的整除性的性质
性质
1
若
a
∣
b
，
b
∣
c
，则
a
∣
c
性质
2
若<
/p>
c∣a，c∣b，则
c∣(a±b)
性质
3
若
b
∣
a,
n
为整数，则
b
∣
na
6
、同余
定义
4
设
m
是大于
1
的
整数，如果整数
a
，
b
的差被
m
整除，我们就说
a<
/p>
，
b
关于模
m<
/p>
同余，记作
a
≡
b(mod m)
7
、同余的性质
性质
1
如果
a
≡
b(mod m)
，
c
≡
d(mod
m)
，
那么
a
±
c
≡
b<
/p>
±
d(mod m)
，
< br>ac
≡
bd(mod m)
性质
2
如果
a
≡
b(mod
m)
，那么对任意整数
k
有
ka
≡
kb(mod m)
2
性质
3
如
果
a
≡
b(mod
m)
，那么对任意正整数
k
有
ak
≡
bk(mod m)
性质
4
如果
a≡b(mod m)，
d
是
a
，
b
的公约数，
a
b
m
mod
d
d
m,
d
< br>
那么
二、例题精讲
例
1
设
m<
/p>
和
n
为大于
0<
/p>
的整数，且
3m+2n=225.
如果<
/p>
m
和
n
的最
大公约数为
15
，求
m+n
的值
(
第
11
届“希望杯”初一试题
)
解：
(1)
因为
(m,n)=15,
故可设
m=15a
，
n=15b
< br>，
且
(a,b)=1
因为
3m+2n=225
，所以
3a+2b=15
因为
a,b<
/p>
是正整数，
所以可得
a=1,b=6
或
a=b=3
，
但
(a,b)=1
，所以
a=1,b=6
从而
m+n=15(a+b)=15 7=105
评注：
1
、遇到这类问题常设
m=15a
，
n=15b
，且
(a,b)=1
，
这样可把问题转化为两个
互质数的求值问题。
这是一种常用方法。
2
、思考一下，如果将<
/p>
m
和
n
的最大公
约数为
15
，改成
m
< br>和
n
的最小公倍数为
45
，问题如何解决？
例
2
有若干苹果，两个一堆多一个，
3
个一堆多一个，
4
< br>个一
堆多一个，
5
个一堆多一个
，
6
个一堆多一个，问这堆苹果最少
有
多少个？
分析：将问题转化为最小公倍数来解决。
解
设这堆苹果最少有
x
个，依题意得
3
x
2
q
1
1
x
1
2
< br>q
1
x
1
3
q
x
3
q
1
2
2
x
< br>4
q
3
1
即
x
< br>
1
4
q
3
x
5
q
1
x
1
5
q
4
4
< br>
x
1
6
q
5
x
6
q
5
1
由此可见，
x-1
是
2
，
3
，
4
，
5
，
6
的最小公倍数
因为
[2,3,4,5,6]=60
，所以
x-1=60
，即
x=61
答：这堆苹果最少有
61
个。
例
3
自然数
a
1
，
a
2<
/p>
，
a
3
，
…，
a
9
，
a
10
的和
1001<
/p>
等于，
设
d
为<
/p>
a
1
，
a
2
，
a
3
，…，
a
9
，
a
10
的最大公约数，试求
d
的最大值。
解
由于
d<
/p>
为
a
1
，
a
2
，
a
3
，…，
a
9
，
a
10
的最大公约数，
所以
和
a
1
+
a
2
+a
3
+
…
+a
9
+a
10
＝
1001
能被
d
整除，
即
d
是
1001
＝
< br>7
11
13
的约数。
因为
d
a
k
< br>，所以
a
k
≥
< br>d
，
k
＝
1
，
2
，
3
，…，
10
从而
1001
＝
a
1
+a
2
+a
3
+
…
+a
9
+a
1
0
≥
10d
所以
d
<
/p>
1001
101
10
由
d
能整除
1001
得，
d
仅可能取值
1
，
7
，
11
，
13
，
77
，
91
。
因为
1001
能写成
10
个数的和：
91+91+91+91+91+91+91+91+91+182
其中每一个数都
能被
91
整除，所以
d
能达到最大值
91
例
4
某商场向顾客发放
9999
张购物券，每张购物券上印有四位
4
数码，
从
0
001
到
9999
号，
如果号码的前两位之和等于后前两位
之和，则这张购物券为幸运券，如号码
0734
，因
0+7=3+4
，所以
这个号码的购物券为幸运券。证明：这个商场所发购物券中，所
有幸运券的号码之和能被
101
整除。
(
第
7
届初中“祖冲
之杯”
数学邀请赛试题
)
证明：显然
，
9999
的购物券为幸运券，除这张外，若号码
为
n
的购物券为幸运券，则号码为
< br>m=9999-n
的购物券也为幸运
券。由于
9999
是奇数，所以
m
，
n
的奇偶性不同，即
m
≠
n
，由
于
m+n=9999
，相加时不出现进位。就是说，除号码为
9999
的幸
运券外，
其余所有的
幸运券可两两配对，
且每对号码之和为
9999
，
从而可知所有的幸运券的号码之和为
9999
的倍数。
由
101
∣
9999
，
所以所有幸运券的号码之和
能被
101
整除。
< br>评注：
本题是通过将数两两配对的方法来解决。
例
5
在<
/p>
1
，
2
，
3
，…，
1995
这
1995
个数中，找出所有满足条件
的
数来：
(1995+a)
能整除
199
5
a
(
第五届华杯赛决赛试题
)
1995
a
分析：
1995
a
1995
a
< br>因此可以将
1995
a
分子、分母都含有
a
，对
a
的讨论带来不便，
化成
1995
1995
1995
1995
a
，
这样只有分母中含有
a
，<
/p>
就容易对
a
进行讨论。
< br>
1995
a
1995
1995
a
1995
1995
1995
1995
1995
1995
a
1995
a
解
1995
a
5