高中数学竞赛——数论

高中数学竞赛 数论
剩余类与剩余系
1.剩余类的定义与性质
(1)定义1 设m为正整数，把全体整数按对模m的余数分成m类 ，相应m
个集合记为：K
0
,K
1
,?,K
m-1
,其中K
r
={qm+r|q∈Z,0?余数r?m-1}称为模m的一
个剩余类(也 叫同余类)。K
0
,K
1
,?,K
m-1
为模m的全部剩余 类.
(2)性质(ⅰ)
Z??K
i
且K
i
∩K
j
=φ(i≠j).
0?
i
?
m
?1
(ⅱ)每一整 数仅在K
0
,K
1
,?,K
m-1
一个里.
(ⅲ)对任意a、b∈Z，则a、b∈K
r
?
a≡b(modm).
2.剩余系的定义与性质
(1)定义2 设K
0
,K
1
, ?,K
m-1
为模m的全部剩余类，从每个K
r
里任取一个a
r，
得m个数a
0
,a
1
,?,a
m-1
组成的 数组，叫做模m的一个完全剩余系,简称完系.
特别地,0,1,2,?,m-1叫做模m的最小非负 完全剩余系.下述数组叫做模m的绝对
最小完全剩余系:当m为奇数时,
?
时,
?
m?1m?1m?1
,??1,
?
,?1,0,1,
?
,
;当m为偶数
222
mmm
mm
,??1,
?
, ?1,0,1,
?
,?1
或
??
1,
?
,
?
1,0,1,
?
,
.
22
222
(2)性质( ⅰ)m个整数构成模m的一完全剩余系
?
两两对模m不同余.
(ⅱ)若(a,m)=1，则x与ax+b同时遍历模m的完全剩余系.
证明:即证a
0,a
1
,?,a
m-1
与aa
0
+b, aa
1
+b,?,aa
m-1
+b同为模m的完全剩余系,
因a< br>0
,a
1
,?,a
m-1
为模m的完系时,若aa
i
+b≡aa
j
+b(modm),则a
i
≡a
j
( modm),
矛盾!反之,当aa
0
+b, aa
1
+b,?,a a
m-1
+b为模m的完系时,若a
i
≡a
j
(modm) ,则有
aa
i
+b≡aa
j
+b(modm),也矛盾!

1

(ⅲ)设m
1
,m
2是两个互质的正整数,而x,y分别遍历模m
1
,m
2
的完系,则
m
2
x+m
1
y历遍模m
1
m
2
的完系 .
证明:因x,y分别历遍m
1
,m
2
个整数,所以,m
2
x+m
1
y历遍m
1
m
2
个整数.
假 定m
2
x

+m
1
y

≡m
2
x

+m
1
y

(modm
1
m
2
),其中x

,x

是x经历的完系中的数,而
y
,y

是y经历的完系中的数.因(m
1
,m
2
)=1, 所以,m
2
x

≡m
2
x

(modm
1
),m
1
y

≡m
1
y

(modm
2
),从而x

≡x

(modm
1< br>),y

≡y

(modm
2
),矛盾!
3.既约剩余系的定义与性质
(1)定义3如果剩余类K
r
里的每 一个数都与m互质，则K
r
叫与m互质的剩
余类.在与模m互质的全部剩余类中，从每 一类中任取一个数所做成的数组，叫
做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4 ;模12的简系1,5,7,11.
(2)性质(ⅰ)K
r
与模m互质
?< br>K
r
中有一个数与m互质；
证明:设a∈K
r
,(m,a) =1,则对任意b∈K
r
,因a≡b≡r(modm),所以,(m,a)=(m,r)=
(m,b)=1,即K
r
与模m互质.
(ⅱ)与模m互质的剩余类的个数等 于
?(m)
,即模m的一个既约剩余系
由
?(m)
个整数组成(?(m)
为欧拉函数);
(ⅲ)若(a,m)=1,则x与ax同时遍历模m的既约剩余系.
证明:因(a,m)=1 ,(x,m)=1,所以,(ax,m)=1.若ax
1
≡ax
2
(modm ),则有
x
1
≡x
2
(modm),矛盾!
(ⅳ)若a
1
,a
2
,?,a
φ(m)
是
?(m)
个 与m互质的整数,并且两两对模m不同余,
则a
1
,a
2
,…,a< br>φ(m)
是模m的一个既约剩余系.
证明:因a
1
,a
2< br>,?,a
φ(m)
是
?(m)
个与m互质的整数,并且两两对模m不同 余,
所以,a
1
,a
2
,?,a
φ(m)
属于< br>?(m)
个剩余类,且每个剩余类都与m互质,故a
1
,a
2
,?,a
φ(m)

2

是模m的一个既约剩余系.
(ⅴ)设m
1
,m
2
是两个互 质的正整数,而x,y分别历遍模m
1
,m
2
的既约剩余
系,则m< br>2
x+m
1
y历遍模m
1
m
2
的既约剩余系 .
证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y分别
历遍模m1
,m
2
的完系时,m
2
x+m
1
y历遍模m
1
m
2
的完系.由(m
1
,x)=(m
2
,y)=1,
(m
1
,m
2
)=1得(m
2
x, m
1
)=(m
1
y,m
2
)=1,所以,(m
2< br>x+m
1
y,m
1
)=1,(m
2
x+m
1
y,m
2
)=1,故
(m
2
x+m
1
y, m
1
m
2
)=1.反之若(m
2
x+m
1
y, m
1
m
2< br>)=1,则(m
2
x+m
1
y,m
1
)=(m
2
x+m
1
y,m
2
)
=1,所以,(m
2< br>x,m
1
)=(m
1
y,m
2
)=1,因(m
1
,m
2
)=1,所以,(m
1
,x)=(m
2
,y)=1.证毕.
推论1若m
1
,m
2
是两个互质的正整数,则
?
(m
1
m
2
)?
?
(m
1)
?
(m
2
)
.
证明:因当x,y分别历遍模m1
,m
2
的既约剩余系时,m
2
x+m
1
y也 历遍模m
1
m
2
的既约剩余系,即m
2
x+m
1< br>y取遍
?
(m
1
m
2
)
个整数,又x取遍< br>?
(m
1
)
个整数,y取遍
?
(m
2
)
个整数,所以, m
2
x+m
1
y取遍
?
(m
1
)
?
(m
2
)
个整数,故
?
(m
1
m
2
)?
?
(m
1
)
?
(m
2
)
.
推论2 设整数 n的标准分解式为
n?p
1
1
p
2
2
?
p
k
?
1
,?,
?
k
?N
*
),则 有
?
(n)?n(1?
111
)(1?)?(1?)
.
p
1
p
2
p
k
???
???
k
(< br>p
1
,
?
,p
k
为互异素数,
证明:由推 论1得
?
(n)?
?
(p
1
1
)
?
(p
2
2
)?
?
(p
k
k
)
, 而
?
(p
?
)?p
?
?p
?
?1
,
(即从1到
p
?
这
p
?
个数中,减去能被p
整除的数的个数),所以,
?
(n)?(p
1
?
? p
1
?
?1
)(p
2
?
?p
2
?
?1
)?(p
k
?
?p
k
?
?1
)

1122kk
?n(1?
111
)(1?)?(1?)
.
p
1
p
2
p
k
4.欧拉(Euler)与费尔马(Ferm at)定理
欧拉(Euler)定理 设m是大于1的整数,(a,m)=1,则
a
?
(m)
?1(modm)
.
证明:设r
1
,r
2
,?,r
?
(m)
是模m的既约剩余系,则由性质3知ar
1,ar
2
,?,ar
?
(m)
也是

3

模m的既约剩余系,所以, ar
1
ar
2
?ar
?
(m)
≡r
1
r
2
?r
?(m)
(modm),即
a
?
(m)
r
1
r< br>2
?
r
?
(m)
?

r
1
r
2
?
r
?
(m)
,因(
r
1
r
2
?
r
?
(m)
,m)=1,所以,
a
?
(m)
?
1(mod
m
)
.
p
推论(Fermat定理) 设p为素数,则对任意整数a都有
a?a(modp)
.
证明:若(a, p)=1 ,由
?
(p)?p?1
及Euler定理得
a
p?1
?1( modp)
即
a
p
?a(modp)
;若(a, p)≠1,则p|a,显然有
a
p
?a(modp)
.
例1设m>0,证明必有一个仅由0或1构成的自然数a是m的倍数.
证明:考虑数字全为1 的数:因1,11,111,1111,?中必有两个在modm的同一剩
余类中,它们的差即为所求的 a.
例2证明从任意m个整数a
1
,a
2
,?,a
m中,必可选出若干个数,它们的和
(包括只一个加数)能被m整除.
证明:考虑m个数 a
1
,a
1
+a
2
,a
1
+a
2
+a
3
,?,a
1
+a
2
+?+a
m,如果其中有一个数能被
m整除,则结论成立,否则,必有两个数属于modm的同一剩余类,这两 个数的差即
满足要求.
例3设f(x)=5x+2=f
1
(x), fn+1
(x)=f[f
n
(x)].求证:对任意正整数n,存在正整数m,使得2011|f
n
(m).
证明:因f
2
(x)=f[f( x)]=5(5x+2)+2=5
2
x+5×2+2,
f
3
(x )=f[f
2
(x)]=5
3
x+5
2
×2+5×2+2, ?, f
n
(x)=5
n
x+5
n-1
×2+5
n -2
×2+?+2,
因(5
n
,2011)=1,所以,x与f
n
(x)同时历遍mod2011的完系,1?x?2011,
所以,存在正整数m(1?m? 2011)使得f
n
(m)≡0(mod2011),即2011|f
n
(m ).
例4设
a
1
,a
2
,a
3
,?是整数序列,其中有无穷多项为正整数,也有无穷多项为
负整数.假设对每个正整数
n< br>,数
a
1
,a
2
,a
3
,?,a
n
被
n
除的余数都各不相同.证明:在
数列
a
1
,a
2
,a
3
,?
中,每个整数都刚好出现一次.

4

证明:数列各项同时减去一个整数不改变本题的条件和结论,故 不妨设a
1
=0.
此时对每个正整数k必有∣a
k
∣k
∣?k,则取n=∣a
k
∣,
则a
1
≡a
k
≡0(mod n),矛盾.
现在对k归纳 证明a
1
,a
2
,…,a
k
适当重排后是绝对值小于k的k 个相邻整数.k=1
显然.设a
1
,a
2
,…,a
k
适当重排后为-(k-1-i),…,0,…,i (0?i?k-1),由于
a
1
,a
2
,…,a
k
,a
k+1
是(mod k+1)的一个完全剩余系,故必a
k+1
≡i+1(mod k+1), 但
∣a
k+1
∣k+1
只能是i+1或-(k-i),从而a1
,a
2
,…,a
k
,a
k+1
适当重排后是 绝对
值小于k+1的k+1个相邻整数.
由此得到:1).任一整数在数列中最多出现一次;2).若整数u和v (u数列中,则u与v之间的所有整数也出现在数列中.
最后由正负项均无 穷多个（即数列含有任意大的正整数及任意小的负整数）
就得到:每个整数在数列中出现且只出现一次.
例5偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌
坐下,证明至少有两个 人，他们中间的人数在休息前与休息后是相等的。
证明：将座号依顺时针次序记为1,2,?,2n，每个人休息前后的座号记为
(i,j)， 则i与j历遍完全剩余系mod2n。如果两个人(i
1
,j
1
),(i2
,j
2
)休息前后在
他们中间的人数不相等，则有j
2
-j
1
?i
2
-i
1
mod2n，即j
2
-i
2
?j
1
-i
1
(mod2n)，因此，
j -i也历遍完全剩余系mod2n,所以,j-i的和=
?
j?
?
i
≡0(mod2n)，而任一完全剩
余系mod2n的和≡1+2+?+2n-1≡n(2n-1)?0 (mod2n),矛盾！故结论成立.
例6数列{a
n
}定义为: a
0< br>=a(a∈N
*
)，a
n+1
=a
n
+
40
n!
(n∈N).数列{a
n
}中存在无穷
多项可被2011整除.
)
. 证明:因(40,2011)=1,所以,
40
?
(2011 )
?1(mod2011

5

)
时,< br>?
(2011)|n!
,所以,数列{a
n
(mod2011)}构成 模2011的完系,因当
n?
?
(2011
且是周期数列,所以, 数列{a
n
}中存在无穷多项可被2011整除.
例7证明:存在无穷多个正整数n,使得n
2
+1?n!.
证明:引理1对 素数p>2,
p?1(mod4)?
存在x(1?x?p-1)使
x
2
??1(modp)
.
证:充分性:因对1?x?p-1,( p,x)=1,所以,x
p?1
?(x
2
)
(?1)
p?1
2
p?1
2
?1(modp)
,
(x
2
)
p?1< br>2
?

?1(modp)
,所以,
p?1
为偶数,即
p?1(mod4).

2
必要性:因1?x?p-1时,x,2x,?,( p-1)x构成modp的既约剩余系,所以,存在
1?a?p-1,使得ax≡-1(mod p),若不存在a(1?a?p-1), a=x,使ax≡-1(mod p),
p?1
p ?1p?1
2
则这样的a,x共配成对,则有
(?1)?(p?1)!??1(mod p)
,即为奇数,与
22
p?4k?1
矛盾!所以,必存在x(1?x?p -1)使
x
2
??1(modp)
.
引理2形如4k+1(k∈Z)的素数有无限多个.
证：假设形如4k+1的素数只有n个: p
1
,p
2
,
?
,p
n
，则p
1
,p
2
,
?
,p
n
都不是
a=4(p< br>1
p
2
?
p
k
)
2
+1的素因数.
设q是a的一个素因数,则有(2p
1
p
2
?
p
k
)
2
≡-1(modq),因存在1?x?q-1使
2p
1
p
2
?
p
k
≡x(mod q),即x
2
≡-1(modq),所以,由引理1知
q?4k?1
,矛盾！
所以,形如4k+1的素数有无限多个.
回到原题:由引理1,2知,存在无穷多个素数p,使得存在x(1?x?p-1)使
x2
??1(modp)
.即p|x
2
+1,因p>x,所以, p?x!, x
2
+1?x!,因这样的素数p无穷多,所以,
相应的x也无穷多.
例8设f(x)是周期函数,T和1是f(x)的周期且0(1)若T为有理数,则存在素数p,使得

1
是f(x)的周期;
p
6

(2)若T为无理数,则存在各项均为无理数的数列 {a
n
}满足0n+1
n
<1
(n=1,2, …),且每个a
n
都是f(x)的周期.
m
证明 ：(1)设T=(正整数m,n互质,且n?2),因(m,n)=1,所以,m,2m,…,nm构成
n
modn的完系,故存在k∈N
*
使得km≡1(modn),即存在t∈N*
使得km=nt+1,因
km111
f(x)=f(x+kT)=f(x+) =f(x+t+)=f(x+),所以是周期.
nnnn
11
1
设n=kp,其中k∈N, p为素数,则
?k?
是周期.故存在素数p,使是周期.
pn
p
*
(2)当T为无理数时,取a
1
=T,则T为无理数, 0a
k
,使得0k
k-1
<1,且a
k
是周期.对k+1,总存在存在u,v∈N
*
,使得0k
-vk
<1,
取a
k+1
=ua
k
-v,则a
k+1
是无理数且是f(x)的周期,且0k+1
k
<1,递推知存在各
项均为无理数的数列{a
n}满足0n+1
n
<1(n=1,2,…),且每个a
n
都是f(x)的周期.
例9设正整数n?2.求所有包含n个整数的集合A,使得A的任意 非空子集
中所有元素的和不能被n+1整除.
解:设A={a
1
,a
2
,?,a
n
}是满足条件的集合.
S
k
?
?< br>a
i
(k
?
1,2,
?
,n)
,依题意知, 对
i?1
k
任意k=1,2,?,n都有n+1?S
k
,且任意S
k
, S
j
(k≠j)都有S
k
?S
j
( modn+1),所以,{S
k
}包
含了modn+1的所有非零剩余,因对1?i≤ n,整数a
i
,S
2
,S
3
,?,S
n
也 包含了mod(n+1)
的所有非零剩余,所以, a
1
=S
1
≡a
i
(modn+1),即A中任意a
i
≡a
1
(modn+ 1).所以,对任
意1?k?n, a
1
+a
2
+?+a
k
≡ka
1
(modn+1).且ka
1
?0(modn+1),从而 (a
1
,n+1)=1.
取a
1
=a得集合A={a+k
i
(n+1)|k
i
∈Z, 1?i≤n,a∈Z,且(a,n+1)=1}为所求.
例10对任意正整数n,用S(n)表示集合{1,2,?,n}中所有与n互质的元素之和.
证明: 2S(n)不是完全平方数;

7

例11求所有的奇质数p,使得
p|
?
k
p?1
.
k?1
2011
222p?12
例12求所有质数p,使得
p
3< br>|(C
1
p
)?(C
p
)???(C
p
)< br>.
例13设n为大于1的奇数,k
1
,k
2
,?,k
n
是n个给定的整数,对1,2,?,n的每一
个排列a=(a
1
,a2
,?,a
n
),记S(a)=
?
k
i
ai
.证明:存在两个1,2,?,n的排列b和c(b
i?1
n
≠c), 使得n!|S(b)-S(c).
证明:如果对1,2,?,n的任意两个不同排列b和c(b≠c),都有
n!?S(b)-S(c),那么当a取遍所有排列时(共n!个),S(a)遍历模n!的一个完系,
因此,有
?
S(a)
≡1+2+?+n!≡
a
nn
n!(n!?1)n!
?
(modn!) ①, 另一方面,我们有
22
n n
n!(n?1)
n
k
i
?0(modn!)
②. S(a)
=
??
k
i
a
i
?
??k
i
a
i
?
?
k
i
[(n?1)!< br>?
j]?
?
?
2
ai?1i?1ai?1j?1i?1
a
由①
?
S(a)
≡(modn!)与②
?
S(a)≡0(modn!)(因n为奇数)矛盾!故原命题成立.
aa
n!
2
例14
已知m,n为
正整数,且m为奇数,(m,2-1)=1.证明:m|
?
k
n
.
n
k?1
m
证明:
因1,2,?,m构 成modm的完系,(m,2)=1,所以2,4,?,2m也构成
modm的完系,所以
?
(2k)?
?
k(modm)
即
(2?1)
?
k< br>n
?0(modm)
.
nnn
k?1k?1k?1
mmm< br>因(m,2-1)=1,所以
m|
?
k
n
.得证.

k?1
n
m
例15已知x∈(0,1),设y∈(0,1)且对任意正整数n ，y的小数点后第n位数字
是x的小数点后第2
n
位数字.证明:若x是有理数,则y 也是有理数.
例16设A={a
1
,a
2
,…,a
φ(n )
}是模n的一个既约剩余系.如果方程x
2
≡1(modn)
在A中解的个 数为N,求证: a
1
a
2
…a
φ(n)
≡
(?1 )
(modn).

8
N
2

同余方程与同余方程组
1.同余方程(组)及其解的概念
定义1 给定 正整数m及n次整系数多项式
f(x)?a
n
x
n
?a
n? 1
x
n?1
?
?
?a
1
x?a
0

，则同余式f(x)≡0(modm)①叫做模m的同余方程,若a
n
0(modm),则n叫做方程
①的次数.
若x=a是使f(a)≡0(modm)成立的一 个整数,则x≡a(modm)叫做方程①的一个
解,即把剩余类a(modm)叫做①的一个解. < br>若a
1
(modm),a
2
(modm)均为方程①的解,且a
1
,a
2
对模m不同余,就称它们是方
程①的不同解.由此可见,只需在模 m的任一组完系中解方程①即可.
例1解方程2x
2
+x-1≡0(mod7).
解:取mod7的完系:-3, -2,-1,0,1,2,3,直接验算知x≡-3(modm)是解.
例2求方程4x
2
+27x-12≡0(mod15).
解:取mod15的完系:-7, -6,?,-1,0,1,?,7,直接验算知x≡-6,3(modm)是解.
2.一次同余方程
设m?a,则ax≡b(modm),叫模m的一次同余方程.
定理1当(a,m)=1时,方程ax≡b(modm)必有解,且解数为1.
证明:因当(a,m)=1时,x与ax同时遍历模m的完系,所以,有且仅有一个x使得
ax≡b(modm).即x≡a
-1
b(modm).
定理2方程ax≡ b(modm)有解
?
(a,m)|b,且有解时其解数为(a,m),及若x
0是一
个特解,则它的(a,m)个解是
x?x
0
?

m
t(modm),t?0,1,?,(a,m)?1
.
(a,m)
9

例3解方程6x≡10(mod8).
解:因(6,8)=2,且-1是一个特解,所以,方程6x≡10(mod8)的解为:
x??1?4t(mod8),t?0,1
即
x??1,3(mod8)
.
例4解方程12x≡6(mod9).
因(12,9)=3,且-1是一个特解,所以,方程12x≡6(mod9)的解为:
x? ?1?3t(mod8),t?0,1,2
即
x??1,2，,5(mod8)
.
3.同余方程组
定义3给定正整数m
1
,m
2
,?,m< br>k
和整系数多项式f
1
(x),f
2
(x),?,f
k
(x),则同余式组
?
f
1
(x)?0(modm
1< br>)
?
f(x)?0(modm)
?
22
②,叫做同余方程组. 若x=a是使f
j
(a)≡0(modm
j
)(1?j?k)
????
?
?
?
f
k
(x)?0(modm
k< br>)
成立的一个整数,则x≡a(modm)叫做方程组②的一个解,即把剩余类a(modm)叫
做②的一个解.其中m=[m
1
,m
2
,?,m
k
].
?
x?3(mod7)
例5解方程组
?
.
?
6x?10(mod8)
解:由例3知6x≡10(mod8)的解是
x??1,3(mod 8)
.所以,原解方程组
?

?
x?3(mod7)
?x?3(mod7)
?
x?31(mod7)
?
?
或
?
或
x?3(mod56)?x?31,3(mod56)
.
?
?< br>x??1(mod8)
?
x?3(mod8)
?
x?31(mod8)
中国剩余定理:设K?2,而m
1
,m
2
,?,m
k
是K个两两互质的正整数，令
M=m
1
m
2
?m
k=m
1
M
1
=m
2
M
2
=?=mk
M
k
，则对任意整数a
1
,a
2
,?,a< br>k
下列同余式组：
?
x?a
1
(modm
1
)
?
x?a(modm)
?
22
-1-1-1
?
③的正整数解是x≡a
1
M
1
M
1
+a
2
M
2
M
2
+?+a
k
M
k
M
k< br>(modM).
?
??
?
?
x?a
k
(m odm
k
)
其中M
j
-1
满足M
j
Mj
-1
≡1(modm
j
)(1?j?k),即M
j
对 模m
j
的逆.

10

证明:(1)对1?j?k,因m
j
|M
i
(i≠j) ,m
j
|M,所以x≡a
j
M
j
M
j
-1
≡ a
j
(modm
j
).
(2)设x,y都是同余式组的解,即x≡ a
j
(modm
j
),y≡a
j
(modm
j)(1?j?k),
则x≡y(modm
j
),即m
j
|x- y,因m
1
,m
2
,?,m
k
两两互质,所以M| x-y即x≡y(modM).
注:(1)存在无穷多个整数x满足同余方程组③,这些x属于同一模m的剩余类;
(2)同 余方程组③仅有一个解x≡a
1
M
1
M
1
-1
+a
2
M
2
M
2
-1
+?+a
k
M< br>k
M
k
-1
(modM).
(3)当(a,m
i
)=1(=1,2,?,n)时,同余方程组
?
x?a
?1
a
1
(modm
1
)
?
ax ?a
1
(modm
1
)
?
?
ax?a(modm)
?1
??
x?aa
2
(modm
2
)
22
?
??
仍然具有定理结论.
?
???
?
???< br>?1
?
x?aa
k
(modm
k
)
?
ax?a
k
(modm
k
)
?
?
这在数论解题中 具有重要应用.
例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问
物几何”.
?
x?2(mod3)
?
解:设物数x,则有
?
x?3(mod5 )
,这里m
1
=3,m
2
=5,m
3
=7,M=3 ×5×7=105,所以,
?
x?2(mod7)
?
35×35
- 1
≡2×35
-1
≡1(mod3)
?
35
-1
≡ 2(mod3),
21×21
-1
≡21
-1
≡1(mod5)< br>?
21
-1
≡1(mod3),
15×15
-1
≡ 15
-1
≡1(mod7)
?
15
-1
≡1(mod3), 所以,同余方程组的解为:
x?2?35?2?3?21?1?2?15?1?233?23(mod 105)
,即x=105k+23(k∈N).
例7有兵一队,若分别列5,6,7,11行纵队,则末行人数分别为1,5,4,10.求兵数. < br>?
x?1(mod5)
?
x?5(mod6)
解:设兵数x,则
?
,其中m
1
=5,m
2
=6,m
3
=7,m< br>4
=11,M=2310,
?
x?4(mod7)
?
??
x?10(mod11)
462×462
-1
≡2×462
- 1
≡1(mod5)
?
462
-1
≡3(mod5),

11

385×385
-1
≡385
-1
≡1(mod6)
?
385
-1
≡1(mod6),
33 0×330
-1
≡330
-1
≡1(mod7)
?
330< br>-1
≡1(mod7),
210×210
-1
≡210
-1
≡1(mod11)
?
210
-1
≡1(mod11),所以,同余 方程组的解为:
x?462?3?5?385?4?330?10?210?6371?2111(m od2310)
,
即x=2310k+2111(k∈N).
例8证明:对任意n 个两两互质的正整数:m
1
,m
2
,?,m
n
,总存在n个 连续的自然
数k+1,k+2,?,k+n使得m
i
|k+i(i=1,2,?,n) .
?
k??1(modm
1
)
?
k??2(modm)< br>?
2
证明:由剩余定理知,总存在整数k使得
?
,即存在连续的自然数
?
?
?
?
?
k??n(modm
n
)k+1,k+2,?,k+n使得m
i
|k+i(i=1,2,?,n).
例9 证明:对任意n∈N
*
,存在n个连续正整数它们中每一个数都不是素数的
幂(当然也 不是素数).
证明:因都不是素数的幂时,只能是素数之积.对任意n∈N
*
,取两组不同的素 < br>数p
1
,p
2
,?,p
n
与q
1
, q
2
,?,q
n
,则由剩余定理知存在m∈N
*
,使得 < br>?
m??1(modp
1
q
1
)
?
m??2 (modpq)
?
22
同时成立.于是,n个连续正整数m+1, m+2,?,m+ n中,每一个数都
?
??
?
?
?
m??n(modp
n
q
n
)
有两个不同的素因子.故结论成立.
例10证明:存在 一个含有N(?2)个正整数的集合A,使得A中任意两个数都
互质,且A中任意k(k?2)个数的和 都是合数.
例11证明:存在一个由正整数组成的递增数列{a
n
},使得对任意k ∈N
*
,数列
{k+a
n
}中都至多有有限项为素数.

12

证明:用p
1
,p
2
,p
3
,?表示所有素数从小到大的排列.令a
1
=2,a
2
为 适合
?
x?0(modp
1
)
?
x?0(modp
1
)
?
且大于a的最小正整数a=8,取a适合
23
?
?
x??1(modp
2
)
且大于a
2
的
1
x??1(modp)
2
?
?
x??2(modp)
3
?< br>?
x?0(modp
1
)
?
x??1(modp)
?
2
最小正整数a
2
=38.假定a
1
,a
2
,?,a
n
都已确定,则取a
n+1
适合
?
且大
??
?
?
?
x??n(modp
n?1
)
于an
的最小正整数,由剩余定理知满足条件的a
n+1
存在.则上述递推关系定义的
数列{a
n
}满足题意:因对任意k∈N
*
,当n?k+1时,都有 k+a
n
≡0(modp
k+1
),
由{a
n
} 递增可知{k+a
n
}从第k+2项起每一项都是p
k+1
的倍数,且都大于 p
k+1
,所以,
数列{k+a
n
}中至多有k+1项为素数.
例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中
出现一次，且对任意 正整数k，该数列的前k项之和是k的倍数？
解:取a
1
=1,假设a
1< br>,a
2
,?,a
m
都已确定,令t为不在a
1
,a< br>2
,?,a
m
中出现的最小正
整数, S=a
1
+a
2
+?+a
m
.由剩余定理知存在无穷多个r∈N
*
,使得
?
a
1
?r?0(mod2)
?
S?r?0(modm?1 )
成立.(如a=1,取t=2,适合且r>1,2得r=3).
?
1
?< br>a?r?t?0(mod3)
?
1
?
S?r?t?0(modm?2)
a
1
,a
2
,?,a
m
}
,令a
m+1
=r, a
m+2
=t,则这样得到的数列取这样的r,使得r>t且r>max{
{a
n
}满足要求.
例13证明:存在一个n∈N
*
,使得对任意整数k,整数k
2
+k+n没有小于2011的
质因数.
例14证明:存在k∈N
*
, 使得对任意n∈N
*
,数2
n
k+1都是合数.
例15设m∈N
*
,n∈Z,证明:数2n可以表为两个与m互素的整数之和.


13