高中数学竞赛数论

高中数学竞赛 数论
剩余类与剩余系
1.剩余类的定义与性质
(1)定义1 设m为正整数，把全体整数按对模m的余数分成m类，相应m个
集合记为：K< br>0
,K
1
,…,K
m-1
,其中K
r
={q m+r|q∈Z,0≤余数r≤m-1}称为模m的一个
剩余类(也叫同余类)。K
0
,K
1
,…,K
m-1
为模m的全部剩余类.
(2)性质(ⅰ)< br>Z??K
i
且K
i
∩K
j
=φ(i≠j).
0?
i
?
m
?1
(ⅱ)每一整数仅在K
0
,K< br>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为偶数
2 22
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),也矛盾!

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

+m
1
y

≡m
2
x

+m
1y

(modm
1
m
2
),其中x

,x

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

,y

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

(modm
1
),m
1
y

≡m
1
y


(modm
2
),从 而x

≡x

(modm
1
),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互质
?
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),矛盾!
(ⅳ)若< br>a
1
,
a
2
,…,
a
φ(m)
是< br>?(m)
个与m互质的整数,并且两两对模m不同余,
则
a
1
,
a
2
,…,
a
φ(m)
是模m的一个既约剩余系. 证明:因
a
1
,
a
2
,…,
a
φ(m )
是
?(m)
个与m互质的整数,并且两两对模m不同余,

所以,
a
1
,
a
2
,…,
a
φ(m)属于
?(m)
个剩余类,且每个剩余类都与m互质,故
a
1
,< br>a
2
,…,
a
φ
(m)
是模m的一个既约剩余系.
(ⅴ)设m
1
,m
2
是两个互质的正整数,而x,y分别历遍模m< br>1
,m
2
的既约剩余
系,则m
2
x+m
1< br>y历遍模m
1
m
2
的既约剩余系.
证明:显然,既约剩余系 是完系中所有与模互质的整数做成的.因x,y分
别历遍模m
1
,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
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< br>2
)=1,则(m
2
x+m
1
y,m
1
)= (m
2
x+m
1
y,m
2
)
=1,所以,(m< br>2
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
)?
?
(m1
)
?
(m
2
)
.
证明:因当x,y分别历 遍模m
1
,m
2
的既约剩余系时,m
2
x+m
1< br>y也历遍模m
1
m
2
的既
约剩余系,即m
2
x+m
1
y取遍
?
(m
1
m
2
)
个整数,又x取遍
?
(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
(
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)与费 尔马(Fermat)定理
欧拉(Euler)定理 设m是大于1的整数,(
a
, m)=1,则
a
?
(m)
?1(modm)
.
证明:设r
1
,r
2
,…,r
?
(m)
是模m的既约剩余系, 则由性质3知
a
r
1
,
a
r
2
,…,a
r
?
(m)
也是模m的既约剩余系,所以,
a
r< br>1
a
r
2
…
a
r
?
(m)
≡r
1
r
2
…r
?
(m)
(modm),即
a
?
(m)
r
1
r
2
?r
?
( m)
?

r
1
r
2
?r
?
(m)
,因(
r
1
r
2
?r
?
(m)
, m)=1,所以,
a
?
(m)
?1(modm)
.
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)< br>.
例1设m>0,证明必有一个仅由0或1构成的自然数
a
是m的倍数. < br>证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm的同一
剩 余类中,它们的差即为所求的
a
.
例2证明从任意m个整数
a
1< br>,
a
2
,…,
a
m
中,必可选出若干个数,它们的和
(包括只一个加数)能被m整除.
证明:考虑m个数
a
1
,
a
1
+
a
2
,
a
1
+
a
2
+
a
3
,…,
a
1
+
a
2< br>+…+
a
m
,如果其中有一个数能被m
整除,则结论成立,否则,必有 两个数属于modm的同一剩余类,这两个数的差即满
足要求.
例3设f(x)=5x+2=f
1
(x), f
n+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, < br>因(5
n
,2011)=1,所以,x与f
n
(x)同时历遍mod2 011的完系,1≤x≤2011,

所以,存在正整数m(1≤m≤2011)使得f
n
(m)≡0(mod2011),即2011|f
n
(m).
例 4设
a
1
,a
2
,a
3
,L
是整数序列, 其中有无穷多项为正整数,也有无穷多项为
负整数.假设对每个正整数
n
,数
a
1
,a
2
,a
3
,L,a
n
被
n
除的余数都各不相同.证明:在
数列
a
1
,a
2
,a
3
,L
中,每个整数都刚好出现一次.
证明:数列各项同时减去一个 整数不改变本题的条件和结论,故不妨设a
1
=0.
此时对每个正整数k必有∣ak
∣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
=
a< br>(
a
∈N
*
)，
a
n+1
=
an
+
40
n!
(n∈N).数列{
a
n
}中存 在无穷
多项可被2011整除.
证明:因(40,2011)=1,所以,
40?
(2011)
?1(mod2011)
.
因当
n?
?
(2011)
时,
?
(2011)|n!
,所以,数列{
a
n
(mod2011)}构成模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)
.
证
以,
x(?1)
p?1
:充
p?1
2
分性:因
p?1
2
对
?

1≤x≤
p
-1,(
p
,x) =1,所
?(x
2
)?1(modp)
,
(x
2
)
p?1
2
?1(modp)
,所以,
p?1
为偶数,即p?1(mod4).

2
必要性:因1≤x≤
p
-1时,x, 2x,…,(
p
-1)x构成modp的既约剩余系,所以,
存在
1≤
a
≤
p
-1,使得
a
x≡-1(mod p
),若不存在
a
(1≤
a
≤
p
-1), a
=x,使
a
x≡-1(mod
p
),
p?1< br>p?1p?1
2
(?1)?(p?1)!??1(modp)
则这样的
a
,x共配成对,则有,即为奇数,
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
，则
p1
,p
2
,…,p
n
都不是

a
=4(
p
1
p
2
…p
k
)
2
+ 1的素因数.
设
q
是
a
的一个素因数,则有(2
p
1
p
2
…p
k
)
2
≡-1(mod
q
),因 存在1≤x≤
q
-1使
2
p
1
p
2
…p
k
≡x(mod
q
),即x
2
≡-1(mod
q
),所以,由引理1知
q?4k?1
,矛盾！
所以,形如4k+1的素数有无限多个.
回到原题:由引理1,2知,存在无穷多个素数p
,使得存在x(1≤x≤
p
-1)使
x
2
??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
(2)若T为无理数,则存在各项均为无理数的数列{a
n
}满足0n+1n
<1
(n=1,2, …),且每个a
n
都是f(x)的周期.
m
证明：(1)设T=(正整数m ,n互质,且n≥2),因(m,n)=1,所以,m,2m,…,nm
n
构成
mo dn的完系,故存在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
?k?
设n=
kp
,其中
k
∈N,
p
为素数,则是周期.故存在素数p,使是周期.
pn
p
*
(2)当T为无理数时,取
a
1
=T,则T为无理数, 0a
k
,使得0<
a
k
<
a
k-1
<1,且
a
k
是周期.对k+1,总存在存在u ,v∈N
*
,使得0a
k
-v<
a
k
<1,
取
a
k+1
=u
a
k
-v,则
a
k+1
是无理数且是f(x)的周期,且0<
a
k+1
<
a
k
<1,递推知存在各
项均为无理数的数列{
a
n
}满足0 <
a
n+1
<
a
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
?
?
a
i
(k?1,2,? ,n)
,依题意知,
i?1
k
对
任意k=1,2,…,n都有n+1?S
k
,且任意S
k
, Sj
(k≠j)都有S
k
?S
j
(modn+1),所以,{S< br>k
}
包含了modn+1的所有非零剩余,因对1≤i≤n,整数
a
i
,S
2
,S
3
,…,S
n
也包含了
mod (n+1)的所有非零剩余,所以,
a
1
=S
1
≡
ai
(modn+1),即A中任意
a
i
≡
a
1
(modn+1).
所以,对任意1≤k≤n,
a
1
+
a
2
+…+
a
k
≡k
a
1
(modn+1).且k< br>a
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)不是完全平方数;
例11求所有的奇质数
p
,使得p|
?
k
p?1
.
k?1
2011
222p ?12
例12求所有质数
p
,使得
p
3
|(C
1< br>p
)?(C
p
)???(C
p
)
.
例13 设n为大于1的奇数,k
1
,k
2
,…,k
n
是n个给定的 整数,对1,2,…,n的每
一个排列a=(a
1
,a
2
,…,a< br>n
),记S(a)=
?
k
i
a
i
.证明:存 在两个1,2,…,n的排列b和
i?1
n
c(b≠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
n!(n!?1)n!
?
(modn!) ①, 另一方面,我们有
22
nn
?
S(a)
=
??
ka?
??
ka?
?
k[(n?1)!
?
iiiii
a
nn
ai?1i?1a i?1j?1
n!(n?1)
n
j]?k
i
?0(modn!) ②.
?
2
i?1
由①
?
S(a)
≡(mo dn!)与②
?
S(a)
≡0(modn!)(因n为奇数)矛盾!故原命题成
aa
n!
2
立.
例14
已知m,n为
正整数,且m为奇 数,(m,2-1)=1.证明:m|
?
k
n
.
n
mk?1
证明:
因1,2,…,m构成modm的完系,(m,2)=1,所以2,4,…, 2m也构成
modm的完系,所以
?
(2k)?
?
k(modm)
即
(2?1)
?
k
n
?0(modm)
.
nnn
k?1k?1k?1
mmm
因(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={
a1
,
a
2
,…,
a
φ(n)
}是模n的一个既 约剩余系.如果方程x
2
≡1(modn)
在A中解的个数为N,求证:
a
1
a
2
…
a
φ(n)
≡
(?1)
(modn).

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)叫做①的一个解.
若
a1
(modm),
a
2
(modm)均为方程①的解,且
a1
,
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
,则
a
x≡b(modm),叫模m的一次同余方程. < br>定理1当(
a
,m)=1时,方程
a
x≡b(modm)必有解,且解 数为1.
证明:因当(
a
,m)=1时,x与
a
x同时遍历模m的 完系,所以,有且仅有一个x使
得
a
x≡b(modm).即x≡
a
-1
b(modm).
定理2方程
a
x≡b(modm)有解
?
(
a
,m)|b, 且有解时其解数为(
a
,m),及若x
0
m
t(modm),t?0 ,1,?,(a,m)?1
. 是一个特解,则它的(
a
,m)个解是
x?x
0
?
(a,m)
例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
k
和整系数多项式f
1
(x),f
2
(x),… ,f
k
(x),则同余
式组
?
f
1
(x)?0( modm
1
)
?
f(x)?0(modm)
?
22
②,叫做同余方程组.若x=
a
是使f
j
(
a
)≡0(mo dm
j
)(1≤j≤k)
?
?
???
?
?
f
k
(x)?0(modm
k
)
成立的一个整数,则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(mod8)< br>.所以,原解方程组
?

?
x?3(mod7)
?
x ?3(mod7)
?
x?31(mod7)
?
或
?
或
x?3(mod56)?x?31,3(mod56)
.
??
x??1(mod8 )x?3(mod8)x?31(mod8)
???
中国剩余定理:设K≥2,而m
1
,m
2
,…,m
k
是K个两两互质的正整数，令
M=m< br>1
m
2
…m
k
=m
1
M
1
=m
2
M
2
=…=m
k
M
k
，则对任意整 数
a
1
,
a
2
,…,
a
k
下列同 余式组：
?
x?a
1
(modm
1
)
?
x?a(modm)
?
22
-1-1-1
?
③的正整数解是x≡a
1
M
1
M
1
+
a
2
M2
M
2
+…+
a
k
M
k
M
k
(modM).
?
?
?
?
?
x?a
k< br>(modm
k
)
其中M
j
-1
满足M
jM
j
-1
≡1(modm
j
)(1≤j≤k),即M
j
对模m
j
的逆.
证明:(1)对1≤j≤k,因m
j
|M
i
(i≠j) ,m
j
|M,所以x≡
a
j
M
j
M
j
-1< br>≡
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< br>两两互质,所以M| x-y即x≡y(modM).
注:(1)存在无穷多个整数x满足同余方程组③,这些x属于同一模m的剩余类;

< br>(2)同余方程组③仅有一个解x≡
a
1
M
1
M
1< br>-1
+
a
2
M
2
M
2
-1
+…+
a
k
M
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
?
??
仍然具有定理结论.
???
???
??
??
x?a
?1
a(modm)
?
ax?a
k
(modm
k
)
kk
?
这在数论解题中具有重要应用.
例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.求
兵数.
?
x?1(mod5)
?
x?5(mod6)
?
解:设兵数x,则
?
,其中m
1
=5,m
2
=6,m
3
=7,m
4
=11,M=2 310,
?
x?4(mod7)
?
?
x?10(mod11)462×462
-1
≡2×462
-1
≡1(mod5)
?462
-1
≡3(mod5),
385×385
-1
≡385
-1
≡1(mod6)
?
385
-1
≡1(mod6),
330×330
-1
≡330
-1
≡1(mod7)
?330
-1
≡1(mod7),
210×210
-1
≡210
-1
≡1(mod11)
?
210
-1
≡1(mod11) ,所以,同余方程组的解

为:
x?462?3?5?385?4?330?1 0?210?6371?2111(mod2310)
,
即x=2310k+2111(k∈N).
例8证明:对任意n个两两互质的正整数:m1
,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)
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
*
,使得
?
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
}中都至多有有限项为素数.
证明: 用
p
1
,p
2
,p
3
,
…表示所有素数从 小到大的排列.令
a
1
=2,
a
2
为适合

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