玩具公司-观灯

,.
第二讲 整除与同余
一、整数的进位制
1、【十进制数 】给定一个
m
位的正整数
A
，其各位上的数字分别记为
a
m

1
,a
m

2
,

,a
0
，
A
可以表示成
10
的
m1
次多项式， 即
A

a
m

1

10
m

1

a
m

2

10
m
2

a
1

10

a
0
，其中
a
i

{0,1,2,
L
,9},

i01,2,，L,m1
且
a
m
1

0
，简记为
A

a
m

1
a
m
2

a
0
.
2、【
p
进制数】
若十进制正整数
A
可以表示为：
A

a
m< br>
1

p
m

1

a
m< br>
2

p
m

2

a
1

p

a
0
，其中
a
i
{0 ,1,2,L,p1},i0，1,2,L,m1
且
a
m
1

0
，
m
仍然为十进制数，则称
A
为
p
进 制数，记为
A

(a
m

1
a
m

2

a
0
)
p
.
【例题分析】 1、（2008）a是由2005个9组成的2005位数，b是由2005个8组成的2005为数，则a b是（ ）
位数.
A 4000 B 4004 C 4008 4010
2．求满足
abc(abc)
的所有三位数
abc
。
解：由于
100abc999
，则
100

(
abc
)

999
，从而
5abc9
； 3
3
当
abc5
时，
5125(125)
； 当
abc6
时，
6216(216)
；
3 333
当
abc7
时，
7343(343)
； 当
abc8
时，
8512(512)
；
3333< br>当
abc9
时，
9729(729)
；
33
于是所求的三位数只有512.
3．一个四位数，它的个位数字与百位数字相同 。如果将这个四位数的数字顺序颠倒过来（即个位数字与
千位数字互换，十位数字与百位数字互换），所 得的新数减去原数，所得的差为7812，求原来的四位数。
解：设该数的千位数字、百位数字、十位数字分别为
x,y,z
，则
原数
10x10y10zy
①；
32
颠倒后的新数
10y10z10yx
②
32

,.
由②－①得7812＝
999(yx)90(zy)

即
86 8111(yx)10(zy)10(yx)10(zx)(yx)
③
比较③式两端百位、十位、个位数字得
yx8,zx6
.
由于原四 位数的千位数字
x
不能为0，所以
x1
，从而
yx89，又显然百位数字
y9
，
所以
y9,x1,zx67
，所以所求的原四位数为1979.
2
二、整除的概念及其性质
（一）、基本概念
1、定义：设
a, b
是给定的整数，
b0
，若存在整数
c
，使得
abc< br>,则称
b
整除
a
，记作
b|a
，并称
b是
a
的一个约数(或因数)，称
a
是
b
的一个倍数，如 果不存在上述
c
，则称
b
不能整除
a
,记作
b
a
.
2、整除的性质
(1) 若
b|c
且
c|a
，则
b|a
(传递性)；
(2) 若
b|a
且
b|c
，则
b|(ac)
;
若反复运用这一性质，易知
b|a
及
b|c
，则对于任意的整数u,v
有
b|(aucv)
;
更一般，若
a|b
i
，则
a|

cb
i

1
n
ii< br>其中
c
i
Z,i1,2,L,n
；
(3) 若
b|a
，则或者
a0
，或者
|a||b|
;特别地，若
b|a
且
a|b
，则
ab
；
(4) (带余除法定理)
设
a,b
为整数，
b0
，则存在一对整数< br>q
和
r
，使得
abqr
，其中
0rb
，满足以上条件的
整数
q
和
r
是唯一确定.整数
q
称为
a
被
b
除得的商，数
r
称为
a
被< br>b
除得的余数。
注意：
r
共有
b
种可能的取值：0 ,1，……，
b1
；若
r0
，即为
a
被
b整除的情形；
（5）若
n
是正整数，则
x

y

(
x

y
)(
x
nnn1

x
n2
y



xy
n2

y
n1
)
；
(6) 如果在等式

a

b
i

1
i
k

1
nm< br>k
中去掉某一项外，其余项均为
c
的倍数，则去掉项也是
c
的 倍数；
(7) m（m≥2且
mZ
）个连续整数中，有且只有一个是m的倍数；
(8) 任何
n
（n≥2且
nZ
）个连续的整数之积一定是n!的 倍数，特别地，三个连续正整数之积能被6整

,.
除；
（9）若一个整数的未位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能；
（10）一个整数的数码之和能被3（或9）整除，则这个数能被3（或9）整除，否则不能；
（11）若一个整数的未两位数字能被4（或25）整除，则这个数能被4（或25）整除，否则不能；
（12）若一个整数的未三位数字能被8（
或125
）整除，则这个数能被8（
或125
）整除，否则不能；
（13）若一个整数的奇位上的数码之和与偶位上的数码之和 的差是11的倍数，则这个数能被11整除，
否则不能。
（14）① 质数：一个大于1的正整数，如果它的因数只有1和它本身，则称为质数或素数；
② 合数：如果一个正整数包含有大于1且小于其本身的因子，则称这个正整数为合数。
（二）、奇数、偶数的性质
(1) 奇数

奇数=偶数，偶数
< br>偶数＝偶数，奇数

偶数＝奇数，偶数

偶数＝偶数，奇数

偶数＝偶数，
奇数

奇数＝奇数；任意多个偶数的和、差、积仍为偶数，奇数 个奇数的和、差仍为奇数，偶数个奇数的
和、差为偶数.
（2）奇数的平方都可以表示成8m1
的形式，偶数的平方可以表示为
8m
或
8m4
的形式 ，其中
mZ
；
（3）任何一个正整数
n
，都可以写成
n
2
l
的形式，其中
m
为负整数，
l
为偶数。 < br>m
（4）若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积为偶数，则这些 整数中至
少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。
（三）、完全平方数及其性质
能表示为某整数的平方的数称为完全平方数，简称为平方数，平方数有以下性质：
（1）平方数的个位数字只可能是0, 1，4 , 5，6, 9；
（2）偶数的平方数是 4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数只有可能是0或
1；
（3）奇数平方的十位数字是偶数；
（4）十位数字是奇数的平方数的个位数一定是6；

,.
（5）不能被3整除的数的平方被3除余1，能被3整除的数的平方能被 3整除。因而，平方数被9除的
余数为0,1，4,7，且此平方数的各位数字的和被9除的余数也只能 是0,1，4,7；
（6）平方数的正约数的个数为奇数个；
（7）任何四个连续整数的乘积加1，必定是一个平方数。
（四）、格点：数学上把在平面直角坐标系中横纵坐标均为整数的点称为格点或整点.
【例题分析】
1、（2005年11）若
2
6

2
9

2
n
为一个平方数，则正整数
n
.
2、（2009）多项式
3x+3x-1

2

3x+2

9
4
=a
0
+a
1
x+a
2
x
2
+L+a
22
x
22
，则
a
1
+a
3
+a
5
+L+a
21
=

2


3、（2007）设数列

a
n

满足:
a1
=1
，
a
n

1
=5a
n

24a
n

1,n

N



,求证：

a

的各项都是正整数.
n


4 、（2009）证明：平面直角坐标系xoy内存在不在一条直线上的2009个整点， 使得每条直线上至少有
3个整点，且任意两点的距离都是整数.

5、（2008）

,.

6．证明：若正整数
a,b
满足
2
aa
3
bb
，则
ab
和
2a 2b1
都是完全平方数。
22
222
证：已知
2
a a
3
bb

2(ab)(ab)b

（ab
）（
2a2b1
）＝
b
①
222
显然
ab
，令
(a,b)d
，则
a

a1
d
,
b

b
1
d
，
(a
1
,
b
1
)

1

从而< br>ab
＝
(a
1

b
1
)d
，将其 代入①得
2
a
1
d

a
1

b< br>1
3
b
1
d
②
22
因为
d |
2
a
1
d
，所以
d|
(a
1
 b
1
)
，从而
d
a
1
b
1
；
2
而②式又可写成
(
a
1
b
1
)
(2a
1
2b
1
1)b
1
d
；
2
因为
(a,b)d
且
(
a
1
,
b1
)

1
，所以
(
a
1

b
1
,
b
1
)1
(a
1
b
1
)

所以
(
a
1
b
1
)
|d
，从而
a
1
b
1
d
。
所以< br>da
1
b
1
，所以
ab
＝
(a
1
b
1
)dd
，从而
ab
为完全平方数。
2
b
2
b
2
所以
2a2b1
2
 ()
也是完全平方数。
d
d
三、同余的定义及其性质
【定义1】. 设
m
是正整数，若用
m
去除整数
a,b，所得的余数相同，则称
a
与
b
关于模
m
同余，记作< br>ab(modm)
，否则称
a
与
b
关于模
m
不同余，记作
a
例如：
344(mod15)
，
10001 (mod7)
，
9
b(modm)
.
8(mod2)
等等。
当
0bm
时，
ab(modm)
，则称
b< br>是
a
对模
m
的最小非负剩余。
对于固定的模
m
，通常有下面的性质：
性质1.
ab(mod m)
的充要条件是
amtb,tZ
也即
m|(ab)
。
性质2.同余关系满足以下规律：
（1）（反身性）
aa(modm)
；
（2）（对称性）若
ab(modm)
，则
ba(modm)
；

,.
（3）（传递性）若
ab(modm)
，
b c(modm)
，则
ac(modm)
；
（4）（同余式相加）若ab(modm)
，
cd(modm)
，则
acbd(mod m)
；
（5）（同余式相乘）若
ab(modm)
，
cd(m odm)
，则
acbd(modm)
；
注意：① 反复利用（4）（5），可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式 ；
② 特别地，由（5）易推出：若
ab(modm)
，
k,c
为整数且
k0
，则
ac

bc(modm)
；
kk
③ 同余式的消去律一般并不成立，即从
acbc(modm)
未必能推出
ab(mo dm)
，可是我们却有
以下结果：若
acbc(modm)
，则
a

b


mod
(m,c)


.


m


由此可以推出：
（6）若
(c,m)1,acbc(modm)
，则有
ab(modm)
，即在
c
与
m
互素时，可以在原同余式两边约
去
c
而不改变模.
（7）若
ab(modm)
，
d
｜
m
，则
ab(modd)
；
（8）若
ab(modm)
，
d0< br>，则
dadb(moddm)
；
（9）若
ab
(mod
m
i
)(
i
1,2,
L
,
k
)
，则
ab(mod[m
1
,m
2
,L,m
k])
，特别地，若
m
1
,m
2
,L,m
k< br>两两互素时，则有
ab(modm
1
m
2
Lm
k
)
；
性质3.若
a
i

b
i
(mod
m
),
i
1,2,,
k
，则
a


b(modm)
；

a

< br>b(modm)
；
i

1
i
i

1
i
i

1
i
i

1
i
kk
kk
性质4.设
f(x)
是系数全为整数的多项式，若
ab( modm)
，则
f(a)f(b)(modm)
。
这一性质在计算时特别 有用：在计算大数字的式子时，可以改变成与它同余的小数字，使计算大大地简化。
整数集合可以按模
m
来分类，确切地说，若
a
和
b
模
m
同余 ，则
a
和
b
属同一类，否则不属于同一类，
每一个这样的类为模m
的一个同余类。由带余除法，任一整数必恰与0,1,……，
m1
中的一个模
m
同余，
而0,1,……，
m1
这
m
个数彼此模
m
不同余，因此模
m
共有
m
个不同的同余类， 例如，模2 的同余类
共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式
2k
和< br>2k1
（
k
为任意整数）.
【例题分析】
1、（200 6年3）在集合

1,2,3,L,50

的子集
S
中任意 两个元素和都不能被7整除，这样的子集
S
中元素

,.
个数最多的是（ ）
A
22
B
7
C
23
D
6
2、（2005年15）试求最小的正整数
n
，使得对 于任何
n
个连续正整数中，必有一数，其各位数字之和是
7的倍数.


【练习题】
1、已知
p,q
为质数，且
p3q17
，则

p


5q

1
2、由7个数字0,1,2,3,4,5,6组成且能被55整除的最小七位数是
3、
a
为正整数，记

2a1,2a2,2a3
< br>表示
2a1,2a2,2a3
的最小公倍数，以
A
表示它.若< br>2a4

整除
A
，则
a=

4、设
p
是给定的奇质数，正整数
k
使得
k
2pk
也是一个正整数，则
k=
< br>5、对于正整数
n
，如果能找到正整数
a,b
，使
nab ab
，则称
n
为“好数”，则在前100个正整数
中，共有“好数”的个数为
6、设
n
是整数，且
4n17n15
表示两个相邻正整数的积，则
n=

2
7、设
1m99
，
1n99
，则使得
( mn)3mn
是完全平方数的有序整数对（
m,n
）的个数为
2

8．设
k1
是一个奇数，证明：对于任意正整数
n< br>，数
1
k
2
k
n
k
不能被
n2
整除。

9．设
m,n
是正整数，
m2
，证明：（
21
） （
21
）。
mn

,.

10．1987可以在
b
进制 中写成三位数
xyz
，如果
xyz1987
，试确定所有可能的
x,,y,z
和
b
。

11．证明不存在正整数
n
，使
2n
2
+
1，
3n
2
+
1
，6n
2
+
1都是完全平方数。

12．证明：对于任 意正整数
n
，数
1
2005
2
2005
n
2005
不能被
n2
整除。

13．已知
n
为正奇数，求证：
60|6321
.
nnn


14．
设a、b、c为满足不等式1＜a＜b＜c的整数 ，且（ab-1）（bc-1）（ca-1）能被abc整除，求所
有可能数组（a，b，c）
.


【试题参考答案】
一、填空题
1、 当
p2
时，
q5
；当
p11
时，q2
；综上：
p1

或 1
.
5q

113
2、 性质：若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除，
否则不能.设该七位数为
10abcd5
，于是
abcd=15
，< br>11


6ac



bd

21



6ac



bd



，
七位数为：
1042635
.
3、任意连续三个正整数互质，则
A

2a1

2a 2

2a3

，由

a2

A, 得a=1.

,.

2k

p

2n

p
2
p

1

p

p
2

22
，即

，k=
4、设k

pk

n

Z,则

k



n

.
244
2k

p

2n

1


2
2
5、由< br>nabab知，
前101个正整数中共有26个，好数个数：

a1< br>
b1

n1,即n1是合数，
101-26=74 k
2

k

15
6、设
4n17n15

2nk

2nk1

4n2
k1

nk

k1

，故
n

.
15

4k
22
当
k0
时，
n1
；当
k2
时，
n3
；当
k3
时，< br>n9
；
7．解：由于
1m99
，
1n99
可得：
(mn)3mn
＜
(
mn
)

4 (
mn
)

4
(mn2)

222
又
(m

n)

(mn)3mn
，于是
( m

n)

(mn)3mn(mn2)

22 222
若
(mn)3mn
是完全平方数，则必有
(mn)3mn
＝
(mn1)
。
222
然而
(mn)3mn< br>＝
(mn1)
nm1
，于是必有
nm10
， 即
mn1
，
22
此时
n1,2,L,98
，
m2,3,L,99
。
所以所求的有序整数对（
m,n
）共有98对：
(m,n)(2,1),( 3,2),(4,3),L,(99,98)
。
二、简答题
8． 证明：
n1
时，结论显然成立。
设
n2
，记所说的和为A，则 ：
2
A
2

(2
n
)

(3

(
n
1))

(
n
2)

kkkkkk
由k是正奇数，从而结于每一个
i2
，数
i( n2i)
被
i(n2i)n2
整除，故
2A
被
n2
除
kk
得余数为2，从而A不可能被
n2
整除（注意n22
）。
9．证明：首先，当
nm
时，易知结论成立。事实上 ，
mn
时，结论平凡；当
nm
时，结果可由
。
2n

1

2
m
1

1
< br>2
m

1
推出来（注意
m2
）
最后，nm
的情形可化为上述特殊情形：由带余除法
nmpr,0rm
而q0
，由于
2
n
1(2
mq
1)2
r
2
r
1
，从而由若
n
是正整数，则
x
n

y
n

(
x

y
)(
x
n1

x
n2
y



xy
n2

y
n1
)
知
(2
m
1)|(2
mq
1)
；而
0rm
，故由上面证明了的结论 知
(2
m
1)

(2
r
1)
（注意< br>r0
时结论平
mn
凡），从而当
nm
时，也有（
21
） （
21
）。
10．解：易知
xb
198 7,
xyz
25
，从而
x(b1)y(b1)162
，
22

,.
即
(
b
1)[(
b
1)
xy
]

1962

2
3

109
，
2
2
由
b10
知< br>b19
。由
1962
b
1
知
b1963 45
故
9b145
；
又因为
1962

2

3

109
有12个正约数，分别为1,2，3,6，9,18, 109,218,327,654,981,1962，所以
2
b118
，从而< br>b19
。又由
1987

5

19
2
9

19

11
知
x5,y9,z1 1.

11．证明不存在正整数
n
，使
2n
2
+< br>1，
3n
2
+
1
，6n
2
+
1都是 完全平方数。
证明：假设存在这样的正整数
n
，使
2n
2
+
1，
3n
2
+
1
，6n
2
+
1 都是完全平方数，那么（
2n
2
+
1）（
3n
2
+
1）
（
6n
2
+
1）也必定是完全平方数。而（
2 n
2
+
1）（
3n
2
+
1）（
6n
2
+
1）＝36
n
6
+36
n
4
+11
n
2
+1；

(6n

3n)

36
n
6
+36
n
4
+9
n
2
；
(6n

3n

1)

36
n
6
+36
n
4
+12
n
3
+9
n
2
+6
n
+1；
3232
32
所以
(6n

3n)

（
2n
2
+
1）（
3n2
+
1）（
6n
2
+
1）＜
(6n3n1 )
与（
2n
2
+
1）（
3n
2
+
1）（
6n
2
+
1）为
32
完全平方数矛盾。
1 2．证明：对于任意正整数
n
，数
1
2005
2
2005
n
2005
不能被
n2
整除。
证明：只需证2 （
n2
）2（
1
2005
2
2005
n
2005
）即可。
因为若
n
是正整数，则
x
< br>y

(
x

y
)(
x
nnn1< br>
x
n2
y



xy
n2< br>
y
n1
)
；
若
n
是正奇数，则
x

y

(
x

y
)(
xnnn1

x
n2
y



xy
n2

y
n1
)
；
故
n2
｜
2
2005
n
2005
；
n2
｜
3
2005
(n1)
2005
，……，
n2
｜
n
2005
2
2005

所以
n2
｜2（
2
2005
n
2005
）。又 因为
n232
，所以
n2
2，
所以
n2
2（
2
2005
n
2005
）＋2， 即（
n2
） 2（
1
2005
2
2005
 n
2005
）命题得证。
13．已知
n
为正奇数，求证：
60|6321

n nn
证明：因为若
n
是正整数，则
x

y

(
x

y
)(
x
nnn1

x
n2
y



xy
n2

y
n1
)
；
若
n
是正奇数，则
x

y

(
x

y
)(
x
nn
n
n1

x
n2
y



xy
n2

y
n1
)
；
nnnnn
所以
3|63
，
3|21
，从而
3|6321
；

4|62
，
4|31
，从而
4|6321
；
nnnnnn
nnn

5|61
，
5|32
，从而
5|6321
； < br>nnn
又
(3,4,5)1
且
34560
，所以60|6321
。
nnn

,.
14．
设a、b、c为满足不等式1＜a＜b＜c的整数，且（ab-1）（bc-1）（ca-1）能被abc整除， 求所
有可能数组（a，b，c）
.
解 ∵（ab-1）（b c-1）（ca-1）=a
2
b
2
c
2
-abc（a+b+ c）+ab+ac+bc-1 ①
∵abc|（ab-1）（bc-1）（ca-1） ∴存在正整数k,使ab+ac+bc-1=kabc, ②
k=＜＜＜＜

∴k=1.
若a≥3，此时1=-＜矛盾，已知a＞1， ∴只有a=2.
当a=2时，代入②中得2b+2c-1=bc，即 1=＜
∴0＜b＜4，知b=3，从而易得c=5.