当前位置:首页 >> 学科竞赛 >>

高中数学竞赛专题讲座---同余理论及其应用(二)


数论定理
一. 知识要点 1. 欧拉定理和费尔马小定理 缩系的定义:设 m 为正整数,一个模 m 的剩余类称为与模 m 互素的余类,如果它中的数与 m 互素.在与 模 m 互素的各个剩余类中分别取一个代表所构成的集合称为模 m 的一组缩系.很显然,缩系具有以下性 质: 1) m 的缩系中含有 ?(m) ( ?(m) ( 模 个数 是小于 m 的正整数中且与 m 互素的个数) 2) r1 , ? r? ?m ? . 设 ( 是 ? (m)个与 m 互素的整数,则 r1 , ? r? ?m ? 模 m 两两不同余. (3)设 ?a, m? ? 1 ,且 r1 , ? r? ?m ? 是模 m 的 一组缩系,则 ar1 , ar2 , ?, ar? ?m ? 是模 m 的一组缩系. 欧拉(Euler)定理:设 m 是大于 1 的整数,a 为整数,且 ?a, m? ? 1 ,则 a
? ?m ?

? 1?mod m ? .

解:设 x1 , x 2 , ?, x? ?m ? 是模 m 的缩系.因为 ?a, m? ? 1 ,所以 ax1 , ax2 , ?, ax? ?m ? 也是模 m 的缩系.这
? ?m ? ax 两个缩系分别乘起来得 ax1 · 2 ?? ax? ?m ? ? x1 x 2 ? x? ?m ? ?mod m? , x1 x 2 ? x? ?m ? , m ? 1 . 且 从而 a ? 1?mod m ?

?

?

a ? ?m ? ? 1?mod m ? .特别地,取 m 为质数 p,有
费 尔 马( Fermat) 小定理 : 设 p 为 质数, a 为整数 ,p a ,则 a
p ?1

? 1?mo d p ? .它 也常常 写成

a p ? a?mod p ? .这里不需假定 p a,但 p 应为素数.
2. 中国剩余定理(孙子定理) 中国剩余定理:设 m1 , m2 ,? mk 是两两互质的正整数, a1 , a 2 ,?, a k 是任意整数,则同余方程组

? x ? a1 ?mod m1 ?, ? x ? a ?mod m ?, ? 2 2 对模 m1 m2 ? mk 有唯一解. ? ?? ? ? x ? a k ?mod mk ?. ?
解:设 M i ?

m1 m2 ? mk ?i ? 1,2,?, k ? .依题设,有 ?M i , mi ? ? 1 ,由裴蜀定理知,存在整数 bi ,使 mi

得 M i bi ? 1?mod mi ? , i ? 1,2,? k . 对 x ? a1b1 M 1 ? a 2 b2 M 2 ? ? ? a k bk M k , 其 中 ai bi M i 能 被

m1 ,?, mi ?1 , mi ?1 ,?mk 整除,而被 mi 除的余数恰为 a i .从而 x ? ? ai bi M i 是同余方程组的解.又设 x,
i ?1

k

y 均 为 同 余 方 程 组 的 解 , 则 有 m1 x ? y , m 2 x ? y , … , m k x ? y , 即 m1 m2 ? mk x ? y , 亦 即

x ? y?mo dm1 m2 ? mk ? .所以同余方程组对模 m1 m2 ? mk 有唯一解.
3. 威尔逊(wilson)定理

1

威尔逊(wilson)定理:设 p 为质数,则 ? p ? 1?!? ?1?mod p ? . 解:对于任意整数 a,且 1≤a≤p-1,由裴蜀定理知,存在整数 a’,使得 aa'? 1?mod p ? .称 a’为 a 的 数论倒数,且不妨设 1≤a’≤p-1.若有整数 b,满足 ba'? 1?mod p ? ,则将此式两边同乘以 a,有

b ? a?mod p ? .这说明对于不同整数 a,1≤a≤p-1,对应着不同的数论倒数 a’.又若整数 a 的数论倒数
是它自身,则 a ? a ? 1?mod p ? ,亦即 ?a ? 1??a ? 1? ? 0?mod p ? ,故 a ? 1 或 ? 1?mod p ? .当 p ? 2 时,显 然有 ? p ? 1?!? ?1?mod p ? .当 p>2 时,有 2,3,…,p-2 这 p-3 个数恰好配成互为数论倒数的 对数,故它们的积 2 ? 3 ? ?? ? p ? 2? ? 1 4. 拉格朗日定理 设 p 为质数,n 是非负整数,多项式 f ?x ? ? a n x ? ? ? a1 x ? a0 是一个模 p 为 n 次的整系数多项式(即 p
n

p?3 2

p ?3 2

? 1?mod p ? .于是 ? p ? 1?!? 1? 1? ? p ? 1? ? ?1?mod p ? .

an) ,则同余方程 f ?x ? ? 0?mod p ?

(※) ,至多有 n 个解(在模 p 的意义下) .

证明: 我们对 n 用归纳法. n ? 0 时, f ?x ? ? a0 , 当 因为 p a0, 故同余方程 (※) 无解, 命题成立. 设 当 n ? l 时命题成立,则当 n ? l ? 1 时,若命题不成立,即同余方程(※)至少有 l ? 2 个解,设为

x ? c1 , c2 ,?, cl ? 2 ?mo d p ?

①,我们考虑多项式 f ?x ? ? f ?c1 ? ? al ?1 x

?

l ?1

? c1l ?1 ? al x l ? c1l ? ? ? a1 ?x ? c1 ?

?

?

?

l

? c1l ? ? ? a1 ?x ? c1 ? ? ?x ? c1 ??al ?1 x l ? ?? ? ?x ? c1 ?h?x ?

?

②,其中 h ? x ? 是 l 次多项式并且首项系数 al ?1 ,满足 ③,至多有个 l 个解,但由①,②可知同余方

p a l ?1 ,从而由归纳假设知 l 次同余方程 h?x ? ? 0?mod p ?

程③至少有 l+1 个解. x ? c2 , c3 ,?, cl ? 2 ?mod p ? ,矛盾!故当 n ? l ? 1 时命题成立.综上所述,命题得 证. 二. 典型例题 例 1. 已知正整数 k≥2, p1 , p 2 ,?, p k 为奇质数,且 ?a, p1 p 2 ? p k ? ? 1 .证明: a 同于 p1 , p 2 ,? p k 的奇质因数.
? p1 ?1?? p2 ?1??? pk ?1?

? 1 有不

a 证明: ?a, p1 p 2 ? p k ? ? 1 , ?a, p1 ? ? 1 . 由 有 由费尔马小定理,

p1 ?1

? 1?mod p1 ? . k≥2,p2 , p3 ,?, pk 又

p2 , p3 ,?, pk 为奇质数,则

? p1 ? 1?? p2 ? 1??? pk ? 1?
2
?1

? p1 ?1?? p2 ?1??? pk ?1?

为正整数,从而 a
?1

2

? 1?mod p1 ? ,即
? p1 ?1?? p2 ?1??? pk ?1?
?1

? p1 ?1?? p2 ?1??? pk ?1?

? p1 ?1?? p2 ?1??? pk ?1?

p1 a

2

.同理, a

2

能被 P2,P3,…Pk 整除,从而 a

2

不能被

2

p1 , p 2 , p3 ,?, p k 整除.注意到
1(mod4) ,因此 4 不整除 a

? p1 ? 1?? p2 ? 1??? pk ? 1?
2
2 ?1

? p1 ?1?? p2 ?1??? pk ?1?

是一个偶数,则 a
?1

2

? 0或

? p1 ?1?? p2 ?1??? p k ?1?

? p1 ?1?? p2 ?1??? p k ?1?

,故 a
1

2

异于 p1 , p 2 ,?, p k 的奇质因数.所以

a

? p1 ?1?? p2 ?1??? p k ?1?

? ? p1 ?1?? p2 ?1??? pk ?1? ? ? ? p ?1?? p 2 ?1 ? ? a ? 1? ? a ? ? ? ? ? ?
n

2 ?1

??? pk ?1?

2

? ? 1? 有异于 p1 , p 2 ,?, p k 的奇质 ? ?

因数. 例 2. 对于自然数 n, 如果对于任何整数 a, 只要 n a ? 1 , 就有 n a ? 1 , 则称 n 具有性质 P. (34 届 IMO
2 n

预) (1)求证:每个素数 n 都具有性质 P.
p

(2)求证:有无穷多个合数也都具有性质 P.
p ?1

证 : 1 ) 设 n ? p 为 素 数 且 p a ? 1 , 于 是 ?a, p ? ? 1 . 由 费 尔 马 小 定 理 知 p a (

?1 , 而

i 故 即 因此,a ? 1?mod p ? ,i ? 0,1,2,?, p ? 1. 上 a p ? 1 ? a a p ?1 ? 1 ? ?a ? 1? . p a ? 1 , a ? 1?md p ? . o p ?1

?

?

述 p 个同余式累和,得 a
2 p 即 p a ?1.

? a p ?2 ? ? ? a ? 1 ? p ? 0?mod p ? .故 p 2 ?a ? 1??a p ?1 ? a p ? 2 ? ? ? a ? 1? ,

? ?n ? (2)设 n 是具有性质 P 的合数.若 n a ? 1 ,则 ?n, a ? ? 1 .由欧拉定理,有 a ? 1?mod n ? ,又因
n

a n ? 1?mod n ? ,由阶的性质知,a ?n,? ?n ?? ? 1?mod n ? .如果 ?n, ? ?n ?? ? 1,则 a ? 1?m n? ,于是利用(1) od
中证明可得 n a ? 1 .因此,问题化为求无穷多个合数 n,使 ?n, ? ?n ?? ? 1.对任何素数 p≥5,取 p-2 的
2 n

素因数 q,并令 n ? pq .这时 ? ?n? ? ? p ? 1??q ? 1? .因为 q ? p ? 2 ? ,所以 q (p-1).又因 q≤p-2<p,
k 故 p (q-1). 因此, ?n, ? ?n ?? ? 1. 有 对于每个这样的合数 n, n a ? 1 , n ?a ? 1? , 若 则 因而 a ? 1?mod n ? ,
n

?

?

k ? 0,1,2, ? .故 n 2 ?a n ? 1? .因为对于每个素数 p≥5 都可按上述程序得到具有性质 P 的相应合数

n? p ? ,且 p< n? p ? <p2,所以,有无穷多个合数 n 具有性质 P.
例 3. 求所有整数 n≥2,满足:对所有的整数 a,b,且 ?a, n? ? ?b, n? ? 1 , a ? b?mod n? 的充分必要条件 是 ab ? 1?mod n ? . (第 41 届 IMO 预选题) 解:若 n 有奇素因子 p,设 p || n ,记 n ? p ? n1 , a ? N .由中国剩余定理知,存在 x ? Z ,使
a a

x ? 1?mod n? , x ? 2?mod p a ?,则 ?x, n ? ? 1 .取 a ? b ? x ,即知 x 2 ? 1?mod n ? ,从而 4 ? 1?mod p a ? ,
故 p ? 3 , a ? 1. 且 因此 ?5, n ? ? 1 . a ? b ? 5 , 取 即知 25 ? 1?mod n ? , 从而 n 24 , n ? 2,3,4,6,8,12,24 故

3

2,3,4,6,8,12,24 .下证:当 n 取上述值时,满足条件.注意到,当 2 a 时,有 a 2 ? 1?mod 8? ;当 3 a 时,有
. a 2 ? 1?mod 3? , 又 n 24 , 24 ? 2 3 ? 3 , 故 必 有 a 2 ? 1?mo dn ? ( 因 为 ?a, n ? ? 1 ) 对 a, b ? Z , 且

?a, n? ? ?b, n? ? 1 ,a ? b?mod n? , ab ? 1?mod n? . a, b ? Z , ?a, n? ? ?b, n? ? 1 , ab ? 1?mod n? , 则 对 且
则 1 ? a ? ab?mod n ? .从而 n ?a ? b ?a 又 ?a, n ? ? 1 ,有 n ?a ? b ? ,即 a ? b?mod n? .综上,所求 n 的值
2

为 2,3,4,6,8,12,24. 例 4. 求所有正整数 n,满足对所有的正整数 n,存在一个整数 m,使 2 n ?1 是 m ? 9 的因子. (第 39 届
2

IMO 预选题)
2 解:引理 1:若 p 为 4k-1(k≥2)型质数,则不存在 m ? Z ,使 m ? ?9?mod p ? .证明:设 m ? 3m1 ?mod p ?

, m ? 3m1 ?mod p ? (∵ ? p,3? ? 1,∴m1 存在) m1 ? N .又∵ m 2 ? ?91 ?mod p ? , ∴ m12 ? ?1(mod p) .由费

? 1,2 2
j

j

? 1,2 2

? ? 1 ? 2?mod ?2 ? 1?? , ?2 ? 1,2 ? 1? ? 1 , ?2 ? 1,3? ? 1 . 且 证明: 2 ? 1 ? ?2 ? ? 1 ? ?? 1? ∵ ∴ ? 1? ? ?2 ? 1,2? ? 1 .又∵ 2 ? 1 ? ?? 1? ? 1 ? 2?mod 3? ,∴ ?2 ? 1,3? ? ?2,3? ? 1 .对于原题,若
2 马小定理知, ? m1p?1 ? m1 1
2i

? ?

p ?1 2

? ?? 1?

p ?1 2

2 2 矛盾. 引理 2: 1≤i<j 时, 2 ? 1,2 ? 1 ? 1 当 有 ? ?1?mod p? ,
i j

2j

2i

2 j ?i

2 j ?i

2i

2i

2j

? ? 1? ? ?2

2i

? 1,2 ? 1

?

2i

2i

2i

2i

?2

n

? 1 m 2 ? 9 ,n≥2.设 n ? 2 S ? t ,2 t.若 t≥3,则 2 t ? 1 2 n ? 1 ,从而 2 t ? 1 m 2 ? 9 .又必存

??

?

?

??

?

?

??

?

t 在 4k-1 型素数 p,且 p ? 3 , p 2 ? 1 (否则, ? 1 ? 2 ? 1 ? 1 ? 1 ? ? ? 1 ? 1?mod 4? ,矛盾) .此时
t

?

?

p ?m 2 ? 9 ? ,与引理 1 矛盾.故 t=1,从而 n ? 2 S ,且 2 2 ? 1 ? 3 ? 2 2 ? 1 2 2 ? 1 ?? 2 2
S 1 2

?

??

?

?

S ?1

? 1 .由引

?

理 2 及中国剩余定理知, 存在 m1 ? N , m1 ? 2 使

2i ?1

?md ?2 o

2i

? 1 , 2, s-1. m12 ? 1 ? 2 2 i=1, …, 故

??

? ?
i ?1

2

?1 ? 0 m o d

? ?2

2

? 22

? ?
i ?1

2

? 1 ? 0 mod 2 2 ? 1 .令 m ? 3m1 ,有 m 2 ? 9 ? 3 2 m12 ? 1 ? 0 mod 2 2 ? 1 .因此, ?2 n ? 1??m 2 ? 9 ? .综
i

? ?

??

?

? ?

?

S

??

上,所求正整数 n 为 2 的幂次 2i(i=1,2,…) . 数论中存在性问题是最常见的,除了运用数论存在性定理来解决外,还需要有直接构造的能力. 例 5. 证明:每个正有理数能被表示成 题) 证明:设该正有理数为 p. (1)当 p ? ?
3

a3 ? b3 的形式,且其中 a,b,c,d 是正整数. (40 届 IMO 预选 c3 ? d 3

? p ? 1? ? ?2 p ? 1? ?1 ? ,2 ? 时, p ? ,其中 2p-1,2-p,p ? p ? 1?3 ? ?2 ? p ?3 ?2 ?
3 3
3n

?2? ?1 ? ?2? ?1 ? +1 ? Q . (2)当 p≥2 时,由于 ? ? ? ? ,1? ,故有 n ? N ,使 ? ? ? p ? ? ,2 ? ,由(1)有 ?3? ?2 ? ?3? ?4 ?
?

4

? ? 2 ? 3n ? ? ? 2 ? 3n ? ? ? ? p ? 1? ? ? 2 ? ? ? p ? 1 ? 3n ? 3 ? ? ?3? ? ? 3 ? ?? 3 ? ?3? ? 1? ? ? ? .3) p?? ? ? ( 当 p ? ? 0, ? 时, 由于 ? ? ? ?1,4 ? , 故有 n ? N , 3 3 3n ?2? ?2? ? 2? ? ? 2 ? 3n ? ? ? ? ? ? p ? 1? ? ? 2 ? ? 2 ? p ? ? ? ?? 3 ? ? ? ? ?3? ? ? ? ?
3n ? ? 3 ? 3n ? ? ? ? ? ? p ? 1? ? ? 2 ? ? 3 ? p ? 1 ? ? ? 3n ? 3n ? ? ?2? ? ? 2 ? ?? 2 ? ?3? ?1 ? ? ? ? .综上,总有 使 ? ? ? p ? ? ,2 ? , 由 ( 1 ) 有 p ? ? ? ? 3 3 3n 3n ?2? ?2 ? ?3? ?? 3 ? ? ? ? ? ? ? p ? 1? ? ? 2 ? ? 3 ? p ? ? ? ?? 2 ? ? ? ? ?2? ? ? ? ? 3 3

3

3

m, a1 , b1 , c1 , d1 ? Q ? ,使 p ? m 3 ?

a13 ? b13 ?ma1 ? ? ?mb1 ? ? ,设 ma1,mb1,c1,d1 的分母公倍数为 n, c13 ? d13 c13 ? d13
3 3

则取 a ? mna1 ? N , b ? mnb ? N , c ? nc1 ? N , d ? nd1 ? N ,且 p ?

a3 ? b3 .结论成立. c3 ? d 3

说明: 这里是直接构造证明, 首先发现恒等式 p ?

? p ? 1?3 ? ?2 p ? 1?3 , 1 进一步对 p≥2, 0<p≤ 构造. 或 例 3 3 2 ? p ? 1? ? ?2 ? p ?
m

? 6. 证明:不存在非负整数 k 和 m,使得 k! 48 ? 48?k ? 1? .
证明: 注意到 k ? 0 或 m ? 0 时, 上述不定方程无解, 于是, 可设满足上述方程的 k, 为正整数. m (1) 若 k ? 1为合数,设 k ?1 ? pq ,2≤p≤q,注意到,应有 48 | k! .故 k≥6,于是 1<2p≤k,故( k ? 1 )| k! , 进而 k ? 1) 48, ( | 结合 k ? 1≥7, 可知 k ? 1=8, 12, 或 48, 24 分别代入, 两边约去 48 后, 可得矛盾. (2) 若 k ? 1为质数,由威尔逊定理,可知 k! ? ?1?mod k ? 1? ,于是, k ? 1| 47,进而 k ? 1 =47,这要求 46!

46! m ? 1 ? 47 m ,两边模 4,可知 ?? 1? ? 1?mod 4? , 48 46! 46! k 故 m 为偶数.设 m=2k,则由①可知 2 ,而 47 ? 1 ? 2?mod 23? , ? 47 k ? 1 47 k ? 1 ,由 232 | 48 48
+48=48×47m ①,从而 m>1,两边除以 48 可知

?

??

?

故 232 | 47 k ? 1,利用二项式定理 47 ? ?2 ? 23 ? 1? ? 46 k ? 1 mod 23 2 ,从而 23 | k,进而 m≥46,这时,
k

?

?

①式右边比左边大.矛盾. 注:一般地,若 n>4,且 n 为合数,则 n |(n-1),依此可以证明威尔逊定理的逆定理也成立. ! 例 7. 设 p 是质数,证明:存在一个质数 q,使得对任意整数 n,数 n ? p 不是 q 的倍数. (第 44 届 IMO
p

试题) 证明:由于

p p ?1 p p ?1 ? 1 ? p ? p 2 ? ? ? p p ?1 ? p ? 1 mod p 2 .则 中至少有一个质因子 q,满 p ?1 p ?1

?

?

足 q 对 p 的模不等于 1。下面证明 q 为所求.假设存在整数 n,使得 n ? p?mod q ? ,则由 q 的选取,有
2 p

5

n p ? p p ? 1?mod q ? .另一方面,由费马小定理,有 n q ?1 ? 1?mod q ? (由于 q 为质数且 ?n, q ? ? 1 ) .由
2

于 p2

(q-1), p , q ? 1 | p , 有 因此,n ? 1?mod q ? , 从而 p ? 1?mod q ? , 这则导出 1+P+…PP 1≡P
2 p


?

?

(modp) 。由 q 的选取,有 p ? 1?mod q ? ,矛盾.所以,命题成立. 注:此题是第 44 届 IMO 中第二天的压轴题,是本次竞赛中难度最大的一道试题.其困难之处在于寻求一 个合适的质数 q,只需将其取为 p ? 1 的一个恰当的质因子.当年参赛的中国队的 6 名国家队员中仅有 2
p

人解出了此题,本题的难度由此可见. 例 8. 设 p>3 是质数, 1 表示集合{1, …, A 2, p-1}中两两不同的 l 个正整数的乘积之和, A1=1+2+… 即 +(p-1) 2=1· ,A 2+1· 3+…+(p-2) (p-1) ,…,Ap-1=(p-1).证明: ! (1)当 1≤l≤p-2 时, Al ? 0?mod p ? ; 解:设 f ? x ? ? ? x ? 1?? x ? 2???x ? ? p ? 1?? ? x (2)当 1<l<p 且 l 为奇数时, Al ? 0 mod p
p ?1 p ?1 l ?1 l

?

2

?.

? ? ?? 1? Al x p ?1?l , g ?x ? ? x p ?1 ? 1.则同余方程

f ?x ? ? 0?mod p ? 有 p-1 个解 x=1,2,…,p-1.由费马小定理可知 g ?x ? ? 0?mod p ? 也有 p-1 个解
x=1,2,…,p-1.从而同余方程 f ?x ? ? g ?x ? ? 0?mod p ?至少有 p-1 个解.但是 f ? x ? ? g ? x ? ?
p?2 l ?1

? ?? 1? A x
l l ?1 l

p?2

p ?1?l

?

?x ? ? g ?x ? ? ? ?? 1?l Al x p?1?l ? ? p ? 1?!?1 是 p-2 次多项式,故由拉格朗日定理知 f ?x ? ? g ?x ? 的各项系数均能被 p 整
除,即有 ? p ? 1?!? ?1?mod p ? . (这里实际上给出了威尔逊定理的另一种证明) Al ? 0?mod p ? ,于是(1) 得证. f ?x ? ? ?x ? 1??x ? 2???x ? ? p ? 1?? ? ?? x ? 1??? x ? 2???? x ? p ? 1?,

??? x ? p ? ? 1???? x ? p? ? 2????? x ? p? ? ? p ? 1?? ? f ? p ? x? ,即 f ?x? ? f ? p ? x? .将 x 换成-x 即得
f ?? x ? ? f ? p ? x ? , 从 而 x p ?1 ? ? Al x p ?1?l ? ? p ? 1?! ? ? x ? p ?
l ?1 p ?1 p ?2 l ?1 p ?2 p ?1

? ? ?? 1? Al ?x ? p ?
l l ?1 p ?2 l ?1 l

p ?2

p ?1?l

? ? p ? 1?!

①,对①模 p2 并利用(1)可得 x

? ? Al x p ?1?l ? x p ?1 ? ? p ? 1? px p ?2 ? ? ?? 1? Al x p ?1?l mod p 2 ,

?

?



? ?1 ? ?? 1?
p?2 l ?1

l ?1

?A x
l

p ?1?l

2 ? p? p ? 1?x p ? 2 mod p 2 , 从而当 l 为奇数且 1<l<p 时, Al ? 0?mod p ? . 有 说

?

?

明:本例的结论是一个很有用的结论,应用它可解决一些问题.
p ?1 例 9. 确定所有的正整数对(n,p) ,满足:p 是一个素数,n≤2p,且 ? p ? 1? ? 1 能够被 n 整除. (第 40
n

届 IMO 试题) 分析:第 40 届 IMO 是题目很难的一届 IMO,这道数论题是第二天测试的第 1 个题目,但仍然具有极大的

6

难度.这道题实际上是证明 ? p ? 1? ? ?1 mod n
n

?

p ?1

? ,很容易联想到利用阶的思想(但具体实现却存在着
n

重重困难) ,最颇费思量的条件是 n≤2p,莫非它有着某些暗示?

? 解: p=2 时, 当 只有整数 n=1, 满足要求. 2 下面考虑 P 为不小于 3 的奇质数的情形. 这时候, p ? 1? ? 1
为奇数,故 n 只可能为奇数(因为 n 为 ? p ? 1? ? 1 的因子) ,先设 n>1.设 n 的最小质因数为 q ? 3 ,则
n

n 可以表示成 n ? q ? s ,其中 k ? 1,且 q s,s 为奇数(≥1) ,且 s 的每个质因数(如果 s≠1 的话)均
k

大于 q.于是由 ? p ? 1? ? ?1 mod n
n

?

p ?1

? 可知 ? p ? 1?
s

n

? ?1?mod q ? ,再根据费马小定理(注意 p-1 与 q
l

互质) ? p ? 1? ,

qk

? P ? 1?mod q ? . ? p ? 1? ? ?1?mod q ? 设 l 为 p-1 对模 q 的阶, ? p ? 1? ? ?1?mod q ? ∴ 则
s 2s

? 我们又有如下三个关系式: p ? 1? ? ?1?mod q ?, ? p ? 1?
可知 l 2 s, l q ? 1 , l
2

? 1?mod q ?, ? p ? 1?

q ?1

? 1?mod q ? . 根据定理 8,

s,∴l 为偶数且 l ?2 s, q ? 1? .由 q 及 s 的取法,∴ ?2s, q ? 1? ? 2 .故 l=

2. ? p ? 1? ? ?mod q ? . p ? 1 ≡1 ∴ 而 (modq) 只可能是 p ? 1 ? ?1?mod q ? , q ? p . p n , n ? 2 p , , ∴ 故 又 从而 n ? p .题目条件化为 ? p ? 1? ? ?1 mod p
p

?

p ?1

?.若 ? p ? 1?

p

? 1 能被 p 3 整除.但 ? p ? 1? ? 1 ? ? C pj ? ?? 1?
p j ?3

p

p? j

?

p ? 1? ? 1 ? ? C pj ? ?? 1?
p j ?3

p

p? j

2 ? P j ? C P ? ?? 1?

p ?2

? p 2 ? p 2 .它除了最后一项 P2 外每一项均被 P3 整除,矛盾.故 P 只

能等于 3.所求的 ?n, P ? ? ?3,3? ,还有 n=1 的平凡情形满足要求.故所求的一切解 ?n, P ? 为(2,2)(3, , 3)(1,P) 为任意质数) , (P . 三. 训练题 1. 13· (-50)2001+17· 2001 模 1989 的最小非负剩余为 4 .

2. 81 除以一个正整数 n,在它的小数部分的 4 个连续数位上出现了 1995,则满足这样的要求的最小的 n = .

3. 证明数列 11,111,1111,…中无完全平方数. 4. 设 P 为 4k ? 3?k ? Z ? 型的质数,a、b 为整数且 a ? b 能被 P 整除,则 P a, P b .
2 2

5. 不能表示成 am ? bn m, n ? 0为整数 形式的最大正整数是多少?这里 a、b 是给定的两个互质正整数. 6. 设 m >n≥1,求最小的 m ? n ,使得 1000 1978
m

?

?

? 1978 n .
n

7. 已知正整数 m, n 满足 m<n 是偶数,并且 1 ? 2 ? 2 为完全平方数.求证: n ? 2?m ? 1? .
m

8. 满足 a ? 1?mod m ?(这 a 是整数,m>1,且(a、m)=1)的最小正整数 l 称为 a 模 m 的阶.证明:
l

7

(1) 1 ? l ? m ? 1 ; 9. 对素数 p ? 3 ,定义 F ?P ? ?

(2)设正整数 t 使得 a ? 1?mod m ? ,则 l t .
t

?k
k ?1

p ?1 2

120

, f ?P ? ?

1 ? F ?P ? ? (第 34 届 ?? ? , ??x? ? x ? ?x?? .求 f ?P ? 的值. 2 ? P ?

IMO 中国国家队选拔考试) 10. 证明:数列{2n-3},n=2,3,4…中有一个无穷子数列,其中的项两两互质. 11. 证明:存在一个正整数 k,使得对各个正整数 n,数 k ? 2 ? 1 是合数.
n

12. 集合 S={1,2,3,4,5,…,1999},若 S 的一个非空子集的元素之和恰好是 1999 的倍数,则称这 个集为 S 的“好子集”.求 S 的所有 17 元“好子集”个数. 13. 能否找到 1990 个自然数的集合 S,使(1)S 中任意两数互质; (2)S 中任意 k ?? 2? 个数的和为合数. 四. 参考答案 1. 30 因 1989=9×13×17,记原数为 x,则 x≡4(mod13) ,x≡-4(mod17) ,x≡3(mod9) ,从而 x≡ 30(mod1989) 2. 401 设

81 ? 10 k r 10 4 r ? …. 1995…, 81×10k=tn+r, 而 这里 1≤r<n. ∴ ? 0. 1995… ? 1995 ? <1996 ? 199 n n n

95 ?

10 4 r <1996 ? 1995 n ? 10 4 r<1996 n . 1995 n ? 10 4 q ? r ?,0 ? r ?<10 4 . r ? ? 0 , 10 4 1995 n ? n ? 2000 再设 若 则由 n

995 n ? n ? 2000 .若 r ? ? 0 ,则由 10 4 r ? 1995 n ? 10 4 q ? r ? ,可得 r ? q ? 1 ∴ 1996 n>10 4 r ? 10 4 q ? 10 4 .而

1996 n ? 1995 n ? n ? 10 4 q ? r ? ? n ,于是 r ? ? n>10 4
2000 5n ? r ?
4

①,又∵ 5n ? 10 q ? r ? ? 2000 n ,∴
5

?

?

②, 注意意到 5n ? r>r ? ? n>10 , 结合②可得 5n ? r ? ? 10 4 ? 2000 ? 5n ? 10 4 2000 ? r ?>2000 ?

? 10 4 2000 ? r ?>2000 ? n>400 , n ? 401 .而

81 ? 0.2019950 …故 401 是最小的. 401

3. 解:因 11≡3(mod4) ,111=100+11≡3(mod4) ,1111=1100+11≡3(mod4) ,…即数列的每一项 mod4 均余 3,而 ?a ? Z ,a2≡0 或 1(mod4) ,故所给数列中无安全平方数. 4. 解:采用反证法.反设 P a,则 P b,且 a2≡-b2(modp).再注意到 P ≡3(mod4) ,故 ∴ a2

p ?1 是奇数, 2
? ?b p ?1 ? 1?mod p ?

? ?

p ?1 2

? ? b2

?

?

p ?1 2

? ? b2

? ? ?mod p?, 亦即a

p ?1 2

p ?1

? ?b p?1 ?mod p? .又由费马小定理 a

p ?1

?1

? ?b p ?1 ? 1?mod p ? ,∴ 1 ? ?1?mod p ?, p 2 .这不可能,故反设不成立,命题得证.
5. 解:最大的正数整数为 ab ? a ? b .提示:对每个 x ? Z ,可表成 x ? at ? bs 形式,且 t ? {0,1,2…, b-1},从而 x 能表成题目要求形式 ? s ? 0 .
8

6. 解:提示:n≥3,而 5 1978

3

m ?n

? 1 ,∴ 5 3 103 20k ? 1 .又由二项式定理易得 103 20 ? 26?mod 125 ? ,

k 3 ∴ 5 26 ? 1 , 26 ? 1 ? 5 ? 1 ? 1 ?
3 k

?

?

k

?C 5
i ?0 i k

k

2i

? 1 ? 25k ?mod 125 ? .故 5 3 26 k ? 1 ? 5 3 25 k ? 5 k ,

∴k≥5.∴ m ? n ? 20 k ? 100 , m ? n ? ?m ? n? ? 2n ? 100 ? 6 ? 106 .而当 n=3,m=103 时,确有

1000 1978 m ? 1978 n ,故 n+m 的最小值为 106.

1 7. 解: n=2k. m ? k ? 1 时, ? 2 ? 2 ? 1 ? 2 设 当
m n

?

k 2

? 为完全平方米. m<k+1 时, ?2 ? <1 ? 2 当 有
k 2

m

? 2 2 k< ?1 ? 2 k

? <1 ? 2
2

m

? 2 2 k< ?1 ? 2 k ? , 从而 1 ? 2 m ? 2 n 不是完全平方米数. m>k+1 时, 当 若有 1 ? 2 m ? 2 n 不是完全平方米数,
2

设1 ? 2 ? 2
m

2k

? ?a ? 2 k ? ,其中 a 为正整数, a>1.于是 a a ? 2 k ?1 ? 1 ? 2 m .将(*)模 2k+1 便得
2

?

?

m k ?1 k ?1 ? 2 k ?1 ? 2 ? 2 2 k ? 2 a 2 ? 1 mod 2 k ?1 , a ? ?1 m 2 k ?1 . o d 即 又注意到 a>1 , a ? 2 ? 1 , 故 从而 1 ? 2 ? a a ? 2

?

?

?

?

?

? ?

?

2 k ?1 ? 2 k ?1 ? 2 ? 2 2 k ? 2 ? 2 k ?1 ? 2>2 2 k ? 2 ? 1 ,因此 m>2k ? 2>n ,矛盾!综上所述,我们有 n ? 2?m ? 1? .
8. 解: (1)由欧拉定理知 a
? ?m ?

? ?

?

? 1?mod m ? ,故 l ? ? ?m? .注意到 ? ?m? ? m ? 1 .从而1 ? l ? m ? 1 .
t ql ? 4

(2)设 t ? ql ? r , qr ? Z ,0 ? r ? l .则 l ? a ? a

? ?a l ? ? a r ? a r ?mod m ? .由 l 的最小性,知
q

r ? 0 ,从而 l t .
说明:阶的性质便于解决一些涉及方幂的问题,在本讲例 4、6 中用到过. 9. 解:设 120 ? q? p ? 1? ? r ,0 ? r ? p ? 2 .因为 120 与 p ? 1 都是偶数,可知 r 也是偶数.定义 G ? p ? ?
p ?1 2

?k
k ?1

p ?1 2

r

根据费尔马小定理, 对于 k=1, 2……, G? p ? ? ? k r .
k ?1

p ?1 p ?1 ? 1?md p ? . o , k 有 所以,F ? p ? ? G ?P ??mod p ?, f ? p ? ? 1 ? ? ? 2 2 ?

? ? ?P ??mod p ?, f ? p ? ? 1 ? ? F ?P ?? ? 1 ? ? G?P ?? . (1) 有 ? ? ? ? 以下分两种情形讨论. 当 r ? 0 时, G ?P ? ? P ? 1 , f ?P ? ? 1 ? ? G P ? ? 1 ? ?
2 ? P ? 2 ? P ?

2

2

? P ?

2

1 ? G ?P ? ? 1 P ? 1 1 ? P ?1? ? P ?1? ? r r ?? , f ?P ? ? ? ? ? . (2)当 r ? 0 时,且 r 是偶数,所以 modp 有 G ?P ? ? 1 ? 2 ? … ? ? ? mod p ? ?mod p ?? ?? ? 2 ? P ? 2 2P 2P ? 2 ? ? 2 ?
rr

? P ?1? ? P ?1? ? P ?1? r r r ?? ? ?mod p ? , 2G?P ? ? G?P ? ? G?P ? ? 1 ? 2 ? …… ? ? ? ?? ? ? …… ? ?P ? 1? .又因为同余 ? 2 ? ? 2 ? ? 2 ?
r r

r

方程 x ? ?mod p ? 的互不同余的解不起过 r 个, 0 ? r ? P ? 2 ,所以存少存在一个 a ?{1,2,……,P
r

-1},使得 ar≡ 1?mod p ? .有 2a C ?P ? ? ?1 ? a ? ? ?2 ? a ? ? …… ? ?? p ? 1? ? a ? ? 2G ?P ??mod p ? (因为
r r r r

1· a , …… , P - 1 ) · 模 P 两 两 不 同 余 , 它 们 的 构 成 缩 剩 余 系 统 的 一 组 代 表 ) 又 因 为 a,2· ( a .
9

2 a r ? 1 G?P ? ? 0?mod p ? , 2 ( ar - 1 ) ≡ 0?mod p ?, 所以G?P ? ? 0?mod p ? . 对 这 种 情 形 ,
f ? p? ? 1 ? G ?P ?P ? 1 ?? ? ? .而 r=0 当且仅当素数 P≥3,且 ?P ? 1?120 ,则 P 分别为 3,5,7,11,13, 2 ? ? 2

?

?

41,61.记 S={3,5,7,11,13,31,41,61}.故 F(P) =

1 ,P?S 2P 1 ,P?S 2
n n

10. 解:用归纳构造,首选取 23 -3,其次设已取出 k 个数 2 1 ? 3,2 2 ? 3, …… 2 k ? 3 两两互质且
n

> n1 <n2< …… nk ? 3 ,则令 nk ?1 ? ? ?2 n1 ? 3?? ? ?2 n 2 ? 3? …… ? ?2 n k ? 3? ? nk? ?2 n k ? 3? nk .又由欧
拉定理知 2
n

? 2 n i ?3

?

? ? 1?mod ?2 m i ? 3??, i ? 1,2,…k,故 n 2 k ? 1 ? 1?mod ?2 n i ? 3??,即2 n k ? 1 ? 3 ? ?2?mod ?2 n i ? 3??, i ?

k ? 1 ? 3 ? ?2 mod 2 n i ? 3 , i ? 1,2,…k.因此 2 n k ? 1 ? 3,2 n i ? 3 ? 1, i ? 1,2,…k.
11. 解:首先注意到 Fermat 数 Fr ? 2
2r

?

?

??

?

?

? 1 ,其中 F5 ? 2 32 ? 1 ? 641 ? 6700417 ? 641P ,且 641 和 P=

6700417 都是素数.考察同余方程组 x ? 1 mod 2

?

32

?1 ,

?

x ? 1?mod 641? , x ? ?1?mod P ? .由于 232-1,641,P 是两两互素的,由中国剩余
定理知其唯一解为 x ? k mod 2
r

?

?

32

? 1,641, P .即 k ? 1 ? ? ?2 32 ? 1? ? 1 ? 641 ? ? P ?? ? 1 (其中 λ、μ、
n 2 rt

??

ν∈N) .设 n ? 2 ? t (r 为非负整数,t 为奇数) ,令 g ?n ? ? k ? 2 ? 1 ? k ? 2 3,4 时, g ?n ? ? k ? 2
r r r

? 1. (1)当 r=0,1,2,
r r r

2 r ?t

? 1 ? k 2 2 ?t ? 1 ? ?k ? 1? ? k 2 2 ?t ? 1 ? ? 2 32 ? 1 .由于 2 2 ?t ? 1 2 2 ?t ? 1,2 2 ? 1 232 ? 1, 故2 2
r r r

?

?

?

? ?

?

2 ?t <g 故 (2) ?? 1 2 2?tr ?t?? ,22 2r?? 1 232?? , 故22 2r?? 1 gnn, 1 2 2 ? 1 ?n ?, 所以g ?n ? 是合数. 当 r=5 时,g ?n ? ? k 2 ? 1 ? ?k ? 1? ? k ?2 122 11, 2 1 232 11, 故 2 1 g ? ? ? ? 同时 <
r

?

?

32 2 k 2 2 ??tt ? 1 ? ?k ? 1? ? k 2 32tt ? 1 ? 64 ? .由于 641 2 32 ? 1 ,且 2 32 ? 1 2 32t ? 1,641 2 32t ? 1, 故641 g ?n ? .同时1 641 ?n? < <g
r r

?

?

?

?

2 t 2 t 2 t 2 t 所以 g(n)是合数. (3) r ? 6 时,g ?n ? ? k 2 ? 1 ? ?k ? 1? ? ?P? ? 1? 2 ? 1 ? P? ? P? 2 ? 1 ? 2 ? 1 当 1 641 ?n? , < <g
r r r r

?

?

?

?

?

? ?

2 ? P? 2 2 tt ? 1 ? 2 22 tt ? 1 ? P? .由于 2 32 ? 1 2 2 t ? 1, 且P 2 32 ? 1, 有P 2 2 t ? 1, 故P g ?n? .同时 1 ? 1 ? 2 ? 1 ? P? <p<g ?n ? .所以 g(n)
rr rr

?

? ?

?

r

r

是合数.综上所述,对一切自然数 n,g(n)=k· n+1 都是合数. 2 12. 解:将 S 的所有 17 元子集记为 A1、A2、…,An,其中 n ? C1999 .再定义 Tk 为满足下面要求的 17 元
17

子 集 A j ?1 ? j ? n ? 的 集 合 : A j 的 元 素 之 和 ? k ?mod 1999 ??1 ? k ? 1999 ? . 我 们 的 想 法 是 证 明

T1 ? T2 ? … ? T1999 .事实上,只需要证明对一切 1 ? k ? 1998 ,成立 Tk ? Tk ?1 即可.容易验证 1999
10

为质数, (17,1999)=1,因而存在惟一的 s∈{1,2,…1999},使 17s≡1(mod1999) .于是我们按如 下方式构造一个映射: f : Tk ? Tk ?1 .若 A ? Tk (A 为某一个 17 元集合 B ? S,且 B 的元素之和=A 的 元 素 之 和 + 17S≡k + 1 ( mod1999 ) 故 B ? Tt ?1 , 则 定 义 f-1(B) = A . 由 f 为 一 一 映 射 可 得 ,
17 Tk ? Tk ?1 ?1 ? k ? 1998 ? , T1 ? T2 ? … ? T1999 . T1 ? T2 ? ? ? 1999 ? C1999 , T1999 ? ∴ 又 ∴

即 S 的所有 17 元“好子集”的个数为

17 C1999 . 1999

17 C1999 . 1999

13. 解: 1990 是个与年份有关的数, 在大多数情况下均可将其一般化为 n. 由于直接构造所涉及情况太多, 故可考虑归纳构造,只想办法去解决新增加一个数所带来的问题.我们可用一般的 n 代替题中的 1990 来 证明. n 用归纳法. 对 n=1,2 明显成立. 假设 n ? m?? 2? 时, 存在 m 个数 a1, 2, am 满足要求, ? m ? 1 a …, n 时, 考虑在这 m 个数的基础上增加一个数 am+1. t ? 2 ? 1 , 记 可以取代 t 个互不相同的质数 P1, 2, t, P …P
m

满足 Pi a1,a2,…am,1 ? i ? t .再记{a1,a2,…,am}中任取 k ?1 ? k ? m? 个的和(总共七个)分别为 S1, 2, t. S …S 则由中国剩余定理, 可知如下同余方程组有解 x0 ? 1 : a1 a 2 … a m x ? 1 ? S i ? 0?1 ? i ? t ? . 取

a m?1 ? a1 a 2 … a m x0 ? 1 ,则 a m ?1 与 a1…am 均互质,且 a1…am+1 中任意 k(≥2)个包含 a m ?1 的数的和均
可表成 a m ?1 +Si 的形式,这里 i 为{1,2,…t}中某正整数,由 a m ?1 取法,知 Pi 为合数.从而 n =m+1 时,亦可构造 n 个数满足题目要求.
2

?a m?1 ? S i ? ,即 a m ?1 +Si

11


相关文章:
高中数学竞赛专题讲座---复数
高中数学竞赛专题讲座---复数_学科竞赛_高中教育_...专题二 复数与几何 1. 有关轨迹问题: 例 1 已知...(1) 利用复数的三角式,应用三角函数的知识求解. (...
全国高中数学联赛专题讲座
全国高中数学联赛专题讲座_学科竞赛_高中教育_教育...同余, 欧几里得除法,非负最小完全剩余类,高斯函数,...直线束及其应用;二元一次不等式表示的区域; 三角形...
高中数学竞赛专题讲座之二 数列
高中数学竞赛专题讲座之二 数列_学科竞赛_高中教育_教育专区。高中数学竞赛专题讲座之一、选择题部分 1. (2006 年江苏)已知数列 ?an ? 的通项公式 an ? 2 数...
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_教育专区。数学归纳法数学归纳法是用于证明正整数 n 有关的数学命题的正确性的一种...
高中数学竞赛专题讲座——解析几何(二)
高中数学竞赛专题讲座——解析几何(二)_高一数学_数学_高中教育_教育专区。数学竞赛专题练习高考资源网(www.ks5u.com) ,您身边的高考专家《解析几何》 各类竞赛试题...
高中数学竞赛专题讲座---代数极值
高中数学竞赛专题讲座---代数极值_学科竞赛_高中教育_教育专区。代数极值很长时间...4 ? 评注:对于分子与分母均为齐次的分时最值问题,一般最易想到运用柯西不等式...
高中数学竞赛培训专题4---同余式与不定方程
高中数学竞赛培训专题4---同余不定方程_学科竞赛_高中教育_教育专区。竞赛培训专题 7---同余不定方程 同余不定方程是数论中古老而富有魅力的内容....
高中数学竞赛——数论
8 N 2 同余方程与同余方程组 1.同余方程(组)...? a ak (modmk ) 这在数论解题中具有重要应用....高中数学竞赛专题讲座--... 3页 免费 《...
高中数学竞赛专题讲座之五:解析几何(2)
高考资源网——提供高考试题、高考模拟题,发布高考信息题本站投稿专用信箱:ks5u@163.com,来信请注明投稿,一经采纳,待遇从优 高中数学竞赛专题讲座之五: 《解析几何...
高中数学竞赛校本教材[全套](共30讲
高中数学竞赛校本教材[全套](共30讲_学科竞赛_高中...等式的应用 §16 排列,组合 §17 二项式定理...同余 §28 高斯函数 §29 覆盖 §29 涂色问题 §...
更多相关标签: