nbhkdz.com冰点文库

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

时间:2017-08-16


同余理论及其应用
基础知识 一. 定义 定义 1. 设 m 为正整数, 整数 a 和 b 之差可被 m 整除时, 称为 a 和 b 关于模 m 同余, 记作 a ? b(modm). 定义 2. 被正整数 m 除余数相等的所有整数的集合称为模 m 的剩余类。模 m 的剩余类共有 m 个。 定义 3. 在模 m 的 m 个剩余类中各取一个整数作为代表,这些代表的集合称为模

m 的完全剩余系。 定义 4. 绝对值不超过 [

m ] 的模 m 的完全剩余系称为模 m 的绝对最小剩余系。 2

定义 5. 当模 m 的某一剩余类的所有整数均与 m 互素时,则称此剩余类是模 m 的简化类。模 m 的简化类 共有 ? ( m) 个。 定义 6. 在模 m 的 ? ( m) 个简化类中各取一个整数作为代表,这些代表的集合称为模 m 的简化剩余系。 定义 7. 欧拉函数:设 n 为正整数,从 1 到 n 的整数中与 n 互素的整数的个数用 ? (n) 表示,称 ? (n) 为欧拉 ?s ?1 ?2 1 1 1 函数。当 n ? p1 p2 ? ps 时,有 ? (n) ? n(1 ? )(1 ? )...( 1? )

p1

p2

ps

二. 定理 定理 1. a ? b(modm). 的必要充分条件是 a 和 b 被 m 除的余数相等。 定 理 2. I. a ? a(modm); II. 若 a ? b(modm), 则 b ? a(modm); III. 若 a ? b(modm), b ? c(modm), 则

a ? c(modm).
定理 3. 若 a1 ? b1 (modm) , a2 ? b2 (modm) ,则 I. a1 ? a2 ? b1 ? b2 (modm) ;II. a1 ? a2 ? b1 ? b2 2 (modm)

a2 ? b1 ? b2 (modm) ;III. a1a2 ? b1b2 (modm) .
定理 4. 如果 ai ? bi (modm)(i ? 1,2,...,n) ,则 I. a1 ? a2 ? ... ? an ? b1 ? b2 ? ... ? bn (modm) ;II.

a1a2 ...an ? b1b2 ...bn (modm).
推论. 如果 a ? b(modm). n 为任意正整数,则 a n ? b n (modm).

m ). (c, m) 推论. 如果 (c, m) ? 1 , ca ? cb(modm). 则 a ? b(modm).
定理 5. 如果 ca ? cb(modm). 则 a ? b(mod 定理 6. 如果 a ? b(modm). 则 (a, m) ? (b, m). 定理 7. a 和 b 属于模 m 的同一剩余类的充要条件是 a ? b(modm). 定理 8. m 个整数 a1 , a2 ,...,am 是模 m 的完全剩余系的充要条件是 a1 , a2 ,...,am 关于模 m 两两互不同余。 定理 9. 设 f 是正整数 m 的正因数。在模 f 的属于 c 的剩余类中取整数 c, c ? f ,...,c ? ( 是模 m 的

m 个剩余类。 f 定理 10. 与 m 互素的 ? ( m) 个整数是模 m 的简化剩余系的充要条件是这 ? ( m) 个整数关于模 m 两两互不同

m ? 1) f ,则它们 f

余。又设 a1 , a2 ,...,ar 是模 m 的简化剩余系,如果 (c, m) ? 1 ,则 ca1 , ca2 ,...,car 也是模 m 的简化剩余系。 定理 11. 欧拉定理:如果 (a, m) ? 1 ,则 a
? ( m)

? 1(modm)
1

定理 12. 费马小定理: 如果 (a, p) ? 1 , 则 a p ?1 ? 1( m o d 这里不要求 a, p 互素。

其中 p 为素数。 它也常写作: p) , a p ? a(mod p) ,

定理 13. 裴蜀定理: 设 a, b, d 是整数, 则 (a, b) ? d 的充要条件是 d a, d b , 存在整数 u , v 使得 ua ? vb ? d 推论 1. (a, b) ? 1 的充要条件是,存在整数 u , v 使得 ua ? vb ? 1 推论 2. a , b 均为正整数, (a, b) ? 1 的充要条件是,存在正整数 u , v 使得 ua ? vb ? 1 典型例题: 一. 同余与完全平方数 例 1. 设素数 p 满足 p ? 7(mod8) ,证明 p 必不能表作三个平方数之和。 分析 我们利用平方数模 8 的性质进行处理。 证明:设存在三个整数 a, b, c 使 p ? a 2 ? b 2 ? c 2 . 其中 a, b, c 或为偶数,或为奇数。因此下式 a ? 0(mod8),
2

a 2 ? 0(mod8), a 2 ? 1(mod8), a 2 ? 4(mod8), 必居其一。事实上,当 a 是奇数 a ? 4m ? 1 或 a ? 4m ? 3 时,
2 2 2 有 a ? 1(mod8), 当 a 是偶数 a ? 4m 或 a ? 4m ? 2 时,有 a ? 0(mod8), 或 a ? 4(mod8), 同样 b 和 c

也必居下式之一: b 2 ? 0(mod8), b 2 ? 1(mod8), b 2 ? 4(mod8), c 2 ? 0(mod8), c 2 ? 1(mod8), c 2 ? 4(mod8),

c 2 ? 4(mod8), 将 a, b, c 所有可能满足的式子任意组合,只能得到 a 2 ? b 2 ? c 2 ? 0,1,2,3,4,5,6(mod8), 而得不
2 2 2 到 a ? b ? c ? 7(mod8). 因此形如 p ? 7(mod8) 的素数不能表作三个平方数之和。

评注 选择合适的模是处理平方数问题的技巧之一。
2 2

例 2. (2003 年越南数学奥林匹克) 求最大的正整数 n, 使得方程组 ( x ? 1) 2 ? y1 ? ( x ? 2) 2 ? y2 ? ... ? ( x ? k ) 2 ? y

2 2 2 ? y2 ? ... ? ( x ? k ) 2 ? yk ? ... ? ( x ? n) 2 ? yn 有整数解 ( x, y1 , y2 ,..., yn )

分析 我们利用平方数的性质处理问题。
2 3? 时,易知所给的方程组有整数解 ( x ? ?2, y1 ? 0, y2 ? 1, y3 ? 0) ,当 n ? 4 时, ? y1 2解:当 ? y2 n ?? 2x 3 ? 2 2 2 2 2 2 2 2 则 y1 , y 2 , y3 , y 4 奇偶交替出现, 则 2 y2 ? ( y1 ? y3 ) ? 2 且 2 y3 ? ( y2 ? y4 ) ? 2 ? y 2 ? y3 ? 2 x ? 5 , ? y ? y 2 ? 2x ? 7 2 2 2 4 若 则 2 y ? 0(mod8) 2 ? y ? y ? 4( m o 8 d ) 矛盾。同理:若 y , y 为偶数,则 y , y ? y3 , y 为奇数,

1

3

2

1

3

1

3

2

4

为奇数。后面式子又矛盾,所以 n ? 4 无解。显然 n ? 4 无解。 评注 选择适当的模,利用平方数性质是解决平方问题的技巧之一。 二. 费马小定理与欧拉定理
13 例 3. 证明 2730 n ? n

分析 由原式联想到费马小定理。
13 7 5 证明: 2730 ? 2 ? 3 ? 5 ? 7 ? 13 ,由费马小定理, n ? n(mod13) , n ? n(mod7) , n ? n(mod5) ,

n 3 ? n(mod3) , n 2 ? n(mod2) ,而 n13 ? n ? (n 7 ? n)(n 6 ? 1) ? (n 5 ? n)(n8 ? n 4 ? 1) ? (n 3 ? n)(n10 ? n8 ? n 6 ? n 4 ?

n 3 ? n)(n10 ? n8 ? n 6 ? n 4 ? n 2 ? 10并且 n 2 ? n | n13 ? n ,由此可知: k | n13 ? n, k ? 2,3,5,7,13 ,所以原命题成立。
评注 费马小定理是处理此类整除问题的重要工具。
2

例4. (2004年加拿大) p 为奇素数,证明: p ?1 解: 由于 p ? 1 为偶数, 则

?k
k ?1

p ?1

2 p ?1

p( p ? 1) (mod p 2 ). 2 k ?1 2 2 2 由二项式定理:( p ? k ) 2 p?1 ? p 2 p?1 ? ... ? C2 ? ? (k 2 p ?1 ? ( p ? k ) 2 p ?1 ) , p?1 p

?k

p ?1

2 p ?1

?

p?1

2 2 2 p?3 1 2 p ?2 ? p 2 p?1 ? ... ? C2 ? C2 ? k 2 p?1 右侧除最后两项外均被 p 2 整除。因此 k 2 p?1 ? ( p ? k ) 2 p?1 ? p?1 p k p?1 pk

k ?1

1 2 p ?2 k 2 p?1 ? C2 ? k 2 p?1 ? (2 p ? 1) p ? k 2 p?2 (mod p 2 ) 由于1 ? k ? p 由费马小定理 k p?1 ? 1(mod p) p?1 pk

2 p ?2 ? mp2 ? p ? ? p(mo ? (2 p ? 1)k 2 p?2 ? (2 p ? 1) ?12 ? ?1(mod p) ,? (2 p ? 1)k 2 p?2 ? mp ? 1 ,则 (2 p ? 1) p ? k p ?1 p ?1 2 2 p ?1 2 p ?2 )( ? p )(mod p 2 ) ? p ? p ? p 2 ? p( p ? 1) (mod p 2 ). ? mp2 ? p ? ? p(mod p 2 ) 所以 ? k 2 p ?1 ? ? (? p) ? ( 2 2 2 k ?1 k ?1 ? p2 p( p ? 1) 2 2 ?p ? (mod p ). 所以,原结论成立。 2 2

评注 二项式定理也是处理数论问题的重要工具。 三. 同余与不定方程 例 5. (2004 年韩国数学竞赛)证明:方程 3 y 2 ? x 4 ? x 没有正整数解。 分析 我们选择适当的模对 x 进行分类处理问题。 证明:(1)当 x ? 3a ? 1(a ? N ) 时, x ? x ? 2(mod3)
4

而方程左边能被 3 整除,此时无解。(2)

当 x ? 3a(a ? N *) 时, x 4 ? x ? x( x ? 1)(x 2 ? x ? 1) ? 3a(3a ? 1)(9a 2 ? 3a ? 1) ? 3 y 2 ,

? a(3a ? 1)(9a 2 ? 3a ? 1) ? y 2

2 ? a, 3a ? 1,9a ? 3a ? 1 而 (a,3a ? 1) ? 1 , (a,9a 2 ? 3a ? 1) ? 1, (3a ? 1,9a 2 ? 3a ? 1) ? 1 , (3a ? 1)(9a 2 ? 3a ? 1) ? y 2 ,

1,9a 2 ? 3a ? 1 均为完全平方数。而 (3a ? 1) 2 ? 9a 2 ? 3a ? 1 ? (3a) 2 所以此时无解。(3)当 x ? 3a ? 1(a ? N *) 时,

x 4 ? x ? x( x ? 1)(x 2 ? x ? 1) ? 9a(3a ? 1)(3a 2 ? 3a ? 1) ? 3 y 2 ,? 3 | y 2 ? 3 | y. 令 y ? 3c(c ? N *) 则

? 3 | a. 令 a ? 3b(b ? N *) , 则 b(9b ? 1)(27b 2 ? 9b ? 1) ? c 2 与 (2) 类似, a(3a ? 1)(3a 2 ? 3a ? 1) ? 3c 2 , 2 ? b ? t b,9b ? 1,27b 2 ? 9b ? 1均为完全平方数。设 ? (t , m ? N *) 则 9t 2 ? 1 ? m 2 ,即 (3t ? m)(3t ? m) ? 1 2 ?9b ? 1 ? m ?3t ? m ? 1 (3t ? m)(3t ? m) ? 1,所以 ? 方程无整数解。综上所述,原方程无整数解。 ?3t ? m ? 1
评注 方程右边可以进行因式分解,而左边系数为 3,因而选择模 3 对 x 进行分类处理问题。 例 6. (2004 年巴尔干数学奥林匹克) x , y 是质数,解: x ? y ? xy ? 19.
y x 2

分析 我们要充分利用 x , y 是质数的条件。
2 x y 2 解:若 x ? y ,则 xy ? 19 无整数解;若 x ? y ,则 y ? x ? xy ? 19. 由于 x , y 是质数,由费马小

定理 x ? x(mody) ,? y ? x ? xy ? ? x(mody). 即 ? x ? 19(mod y ) ,? y | 19 ? x
y x y 2

①,再由费

马小定理

y x ? y( m o x d )

? y x ? x y ? xy 2 ? y(modx). 即 y ? 19(modx) 1. 若 y ? 19 则 x | y ? 19

②;2. 由①知: y ? 19 ? x ; 由②知: x ? y ? 19 即 y ? x ? 19 ,? y ? x ? 19 ,又 y 为质数。而 x 为
3

奇质数, y 为偶数, x ? 2, y ? 21 与 y 为质数矛盾。所以此时无解;3. 若 y ? 19 ,由 y | 19 ? x 知 y | x
x 17 2 x 17 ?y ? x, 无解; 4. 若 y ? 19 , 则当 y ? 17 时:17 ? x ? x ? 17 ? 19. 易知:x ? 17 时,17 ? x ? 0 ,

无解,? x ? 13 ,当 x ? 13,11,7,5,3 时,两边模 4,知无解; x ? 2 时,左边小于 0,无解;当 y ? 13 时: 两边模 4, x ? 11 ,7,5,3 x ? 2 时,左边小于 0。当 y ? 11时:同理 x ? 7,5,3 无解; x ? 2 时,左边小于 0。当 y ? 7 时: x ? 5,3 无解; x ? 2 时,满足条件。? x ? 2, y ? 7 为一组解。当 y ? 5 时, x ? 3 无解;

5 x ? x 5 ? x ? 5 2 ? 19. x ? 2 时,无整数解;当 y ? 3 时, x ? 2
一组解。综上, x ? 2, y ? 7 ; x ? 2, y ? 3 为解。

3 ? 32 ? 2 3 ? 19 ,? x ? 2, y ? 3 为

评注 在处理有关质数的幂的问题中,费马小定理常发挥重要作用。 四. 同余定理 例 7. 设 p 是奇素数,a 是连续数列 2,3,4,..., p ? 3, p ? 2

①中的任一数,则数列 a,2a,3a,...,( p ? 3)a, ( p ? 2)a, ( p ?

,...,( p ? 3)a, ( p ? 2)a, ( p ? 1)a
相异。 分析 利用 p 为素数

②中必有一个且只有一个数关于模 p 与 1 同余,设此数为 ia,则 i 为①中一数且与 a

证明:因为①中各数均小于 p,p 为素数,所以①中每一个数均与 p 互素。由于 a 是①中某数,故

(a, p) ? 1. 因此,由定理 11,数列 a,2a,3a,...,( p ? 3)a, ( p ? 2)a, ( p ? 1)a 与数列①代表同一类数,也就是
说,数列②表示模 p 的除 p 的倍数外,其余的一切类数。因此②中必有一数 ia(1 ? i ? p ? 1) ,使

ia ? 1(mod p) 。 这个 i 决不能等于 a, 事实上, 如果 i ? a , 则有 a 2 ? 1(mod p) , 从而就有 (a ? 1)(a ? 1) ? 0(mod p)

? 1)(a ? 1) ? 0(mod p) 。由于 p 是素数,且 p ? | 2 ,故 a ? 1 ? 0(modp) 或 a ? 1 ? 0(mod p) ,两者必居其一。但
1 ? a ? p ? 1 ,即 0 ? a ? 1 ? p, 2 ? a ? 1 ? p 。所以不可能有 a ? 1 ? 0(modp) 及 a ? 1 ? 0(mod p) 。
故i ? ? a 另外可以证明 i ? ? p ? 1. 否则如果 i ? p ? 1. 就有 ia ? ( p ? 1)a ? p(a ? 1) ? p ? a ? p ? a(mod p). 但 1 ? a ? p ? 1 ,即 1 ? p ? a ? p ? 1 ,所以 1 ? ( p ? a) ? 1 ? p ? 2 ,因此不可能有 p ? a ? 1(mod p). 所以

i? ? 1. 否则就有 ia ? a ? 1(mod p) ,但这与 1 ? a ? p ? 1 矛盾。这样就证明了数列 ? p ? 1. 再次可以证明 i ?
②中必有一数 ia,有 ia ? 1(mod p) ,而又 i ? ? a ,故 i 必为①中一数且与 a 相异。此外, ? 1. i ? ? p ? 1. i ? 如果①中有两数 i, j (i ? ? j, i ? ? a, j ? ? a), 使 ia ? ja(mod p) ,那么由于 (a, p) ? 1 ,故有 i ? j (mod p) ,但

2 ? i, j ? p ? 2 ,从而有 i ? j ,这与假设 i ? ? j 矛盾。
评注 本题是最基本的结论之一。 例 8. 求证: ( p ? 1)!? ?1(mod p). 这里 p 为奇素数。 分析 我们利用例 1 的结论。 证明:对任意 S ? ? 1,2,..., p ? 1?,都存在唯一的 S 时, S
?1

?1

?? 1,2,..., p ? 1? 使 SS ?1 ? 1(mod p). 注意到 S ? t

? t ?1 . 否则若 S ?1 ? t ?1 ? SS ?1 ? St ?1 (mod p) ,?1 ? St ?1 (mod p). 即 tt ?1 ? St ?1 (mod p), p | t ?1 (t ? S ).

St ?1 (mod p), p | t ?1 (t ? S ). ? p | t ? S 矛盾。又注意到 (S ?1 ) ?1 ? S. 故可以把 1,2,..., p ? 1 中 S 和 S ?1 两两配对,每一
4

对的乘积同余于 1 模 p,由于 x 2 ? 1(mod p) 有且仅有两解 x ? ?1(mod p) ,所以除了 1, ? 1 和自己配对 外,其余 p ? 3 个数恰可配成 评注 本题即威尔逊定理。 五. 同余与其他 例 9. 已知 a1 ? 1, a2 ? 2, an?2 ? ?
p ?2 p?3 对。? ? ? 1(mod p). 2 i ?2

? ( p ? 1)!? 1 ? 1 ? (?1) ? ?1(mod p).

分析 我们只要证明 an 模某一常数不为 0 即可。

?5an?1 ? 3an , 若an ? a n?1为偶数 证明:对一切正整数 n, a n ? 0. ? an?1 ? an , 若an ? a n?1为奇数

证明:若某一个 ak ? 0 ,则对任意正整数 m 有 ak ? 0(modm) ,因此,我们只要找到一个 m,对任 何一个 n 均有 ak ? 4) m) 即可, a1 ? 1( m o d ? 0(mod

a2 ? 2( m o 4 d) a3 ? 3( m o 4 d) 。设 n ? k 时,

则 n ? k ? 1 时, a3k ? 2 ? 1(mo d 4) ,a3k ?1 ? 2(mod4) ,a3k ? 3(mod4) , a3k ?1 ? 5a3k ? 3a3k ?1 ? 1(mod4) 因此对一切 n 均有 ak ? a3k ?2 ? a3k ?1 ? a3k ? 2( m o 4 d) , a3k ?3 ? 5a3k ?2 ? 3a3k ?1 ? 3(mod4) , ? 0(mod4) , 从而原命题成立。 评注 同余是处理此类问题的有效方法之一。 例 10. (1996 年保加利亚)求所有的质数 p, q ,使得 pq 整除 (5 p ? 2 p )(5q ? 2 q )
p p q q p p 解: 如果 p 5 ? 2 , 由费马小定理, p 5 ? 2 , 所以 p ? 3 , 假设 p, q ? 3 , 则 p 5 ? 2 ,q 5 ? 2 。

不失一般性,我们设 p ? q ,则 ( p, q ? 1) ? 1 ,由裴蜀定理,存在正整数 u , v ,使 u (q ? 1) ? vp ? 1 。由费 马小定理 q 5 所以
q ?1

? 2 q ?1 , 所以 q 5

u ( q ? )1

p p ? 2 u ( q ?1) = 5vp?1 ? 2vp?1 = 5(5vp ? 2vp ) ? 3 ? 2vp , 又q5 ? 2 ,

p 3 ? 2 vp

3 3 } , 矛盾。 所以 p, q 之一为 3 。 若 q ? 3, 则 q 5 ? 2 ? 9 ? 13 , 所以 q ? 13 。 类似,p ? {3,13

因此,解 ( p, q) ? (3,3), (3,13), (13,3) 。 练习及参考答案

练习 1. 求证:存在无穷多个这样的正整数,它们不能表示成少于十个奇数的平方和。 分析 对于否定性问题,我们常利用同余。 解:设正整数 n 能够表示成 n ? x1 ? x2 ? ... ? xs ,
2 2 2

①,其中 x i 为奇数, i ? 1,2,...,s,1 ? s ? 9. 若

n ? 2(mod8) ,则由①及 xi2 ? 1(mod8),i ? 1,2,...,s 知 s ? 2(mod8) ,即 s ? 2. 若 s ? 2,3 | n ,则由①及

xi2 ? 0,1(mod3),i ? 1,2 知 x1 ? x2 ? 0(mod3) ,从而 9 | n. 这说明若 n ? 3(mod9) ,则 s ? 2. 综上所述,
被 8 除余 2,被 9 除余 3,即具有形式 72k ? 66, k ? 0,1,2,... 的正整数便不能表示成①,故命题得证。

5

评注 对于某些问题,常常需要多次选择不同的模进行同余处理。 练习 2. 求出大于 1 的整数 n 的个数,使得对任意的整数 a ,都有 n | a 25 ? a 分析 联想例 4,猜想 n 的最大值为 2730。 解:设满足条件的正整数组成集合 S,若 n | a 25 ? a , m | a 25 ? a ,则 [m, n] | a 25 ? a ,因此 S 中全 部数的最小公倍数也属于 S ,即 S 中的最大数是其余每个数的倍数。 m | a 25 ? a ,则 m 的约数也整除

a 25 ? a ,于是只需确定最大数 m ,其一切大于 1 的约数组成集合 S。? m | 2 25 ? 2, m | 325 ? 3 ,并且

(2 25 ? 2,325 ? 3) ? 2 ? 3 ? 5 ? 7 ?13 ,由例 4 ,由费马小定理,易证 2 ? 3 ? 5 ? 7 ? 13 | a 25 ? a ,所以
m ? 2 ? 3 ? 5 ? 7 ? 13 ,集合 S 共有 31 个元素。
评注 利用特殊值法确定最大值,再进行证明是处理竞赛问题的典型技巧。 练习 3. 2340 ? 1(mod341 ) 但 341 ? 11 ? 13 为合数,则称 341 是伪质数,证明:伪质数有无穷多个。 分析 我们想办法构造出具体的表达或递推关系。
m 证明: 已知 341 为伪质数, 假设 m 是伪质数, 下面证明 2 ? 1 是伪质数, 首先, 设 m ? pq , 其中 p, q

为大于 1 的整数, 则 2 m ? 1 ? 2 pq ? 1 ? (2 p ) q ? 1 , 含有因子 2 ? 1 , 并且 1 ? 2 ? 1 ? 2 ? 1, 所以 2 ? 1
p p m m

为合数。 其次, 由于 m | 2

m ?1

22

m

?2

? 1 ? (22 ?1 ? 1)(22 ?1 ? 1) , 而 22 ?1 ? 1 ? 2ms ? 1 ? (2m ) s ? 1 , 可 被 2 m ? 1 整 除 , 因 而 m 2( 2 ?1)?1 ? 1(mod(2m ? 1)) ,所以 2 m ? 1 是伪质数,并且 2 m ? 1 ? m 。由此可知伪质数有无穷多个。
评注 利用递推关系构造是解决无穷解问题的重要构造方法。
2002 练习 4. (第 43 届 IMO 预选题)求最小的正整数 n,使得: x1 ? x2 ? ... ? xn ? 2002 有整数解。 3 3 3

m ?1

m?1

m?1 ?1 ? m s , 设2 其中 s 为大于 1 的正整数, ? 1, 2( 2
m?1

m

?1)?1

? 1 ? 22

m

?2

? 1 ? (22

m ?1

?1

分析 我们先估计出 n 的值,在构造出一组解。
3 2002 解:2002? 4(mod9) ,4 ? 1(mod9) ,2002 ? 667 ? 3 ? 1 , 所以 2002 ? 4 2002 ? 4(mod9) 又

3 3 3 3 3 3 3 3 于是 x1 , x1 ? x2 , x1 ? x2 ? x3 ? 由于 2002? 10 ? 10 ? 1 ? 1 x 3 ? 0,?1(mod9) 其中 x ? Z , ? 4(mod9) ,

? 103 ? 103 ? 1 ? 1 ,则 20022002 ? 2002? (2002667 ) 3 ? (10? 2002667 ) 3 ? (10? 2002667 ) 3 ? (2002667 ) 3 ? (2002667 ) 3
所以 n ? 4 。 评注 选择适当的模,利用同余进行估计是重要的方法之一。 练习 5. (2003 年中国集训队测试)正整数 n 不能被 2, 3 整除,且不存在非负整数 a, b,使得|2 a-3 b| = n。求 n 的最小值。 分析 我们先通过具体赋值猜出 n 值,再进行证明。 解:n = 1 时,|2 1-3 1| = 1;n = 5 时,|2 2-3 2| = 5;n = 7 时,|2 1-3 2| = 7;n = 11 时,|2 4-3 3| = 11;n = 13 时,|2 4-3 1| = 13;n = 17 时,|2 6-3 4| = 17;n = 19 时,|2 3-3 3| = 19;n = 23 时,|2 5 -3 2| = 23;n = 25 时,|2 1-3 3| = 25;n = 29 时,|2 5-3 1| = 29;n = 31 时,|2 5-3 0| = 31;下证 n =
6

35 满足要求,用反证法,若不然,存在非负整数 a, b,使得 |2 a-3 b| = 35。?1?若 2 a-3 b = 35,显然 a ≠ 0, 1, 2,故 a ≥ 3,模 8,得-3 b ≡ 3 ?mod 8?,即 3 b ≡ 5 ?mod 8?,但 3 b ≡ 1, 3 ?mod 8?,不可能。?2? 若 3 b-2 a = 35,易知 b ≠ 0, 1,模 9,得 2 a ≡ 1 ?mod 9?,∵ {2 k ?mod 9?}:2, 4, 8, 7, 5, 1, 2, 4, …,∴ 2 6k ≡ 1, 2 6k + 1 ≡ 2, 2 6k + 2 ≡ 4, 2 6k + 3 ≡ 8, 2 6k + 4 ≡ 7, 2 6k + 5 ≡ 5 ?mod 9?,于是 a = 6k,k 为非负整数,所以 3 -8 2k = 35。再模 7,得 3 b ≡ 1 ?mod 7?,∵ {3 k ?mod 7?}:3, 2, 6, 4, 5, 1, 3, 2, …,故 b = 6k/,k/为正 ? 3 3k ?-2 3k = 1 ? 3 3k ?-2 3k = 5 整数,∴ 3 6k ?-2 6k = 35,?3 3k ?-2 3k ??3 3k ? + 2 3k ? = 35,∴ ? 3k ? 或 ? 3k ? 于 3k + 2 = 35 + 2 3k = 7 ? 3 ? 3
b

是,3 3k ? = 18 或 6,不可能。综上可知,nmin = 35。 评注 对于不定方程无解的问题常用同余处理。 练习 6. (2004 年亚太地区数学竞赛)证明:对于任意正整数 n , ?

? (n ? 1)!? 是偶数。 2 ?n ?n? ?

分析 当 n 和 n+1 是合数时,容易处理,我们只要处理 n 和 n+1 之一是素数的情况。 证明:对于 n = 1, 2, 3, 4, 5 我们有 ? 2 =0,显然为偶数。我们考虑 n ≥ 6. 如果 n 和 n+1 是 ?n ?n? ? 合数,则它们 一定整除 (n-1)! ,并且互素。所以它们的乘积整除 (n-1)!. 由于 n, n+1 中只有一个是偶数, 对于 m ≥ 6, (m-2)! 所含的 2 的幂指数大于 m 所含的幂指数,所以 ?

? (n ? 1)!?

? (n ? 1)!? 是偶数. 我们最后考虑 n+1 = p 2 ?n ?n? ?

为一个素数,和 n = p 为一个素数. 如果 n+1 = p, 则 p-1 是一个合数,所以 p-1 整除(p-2)!. 令 k =

( p ? 2)! ,由威尔逊定理 (p-2)! = 1(mod p), 所以 k(p-1) = 1( mod p),因此 k = -1(mod p).所以 p ?1

? k ? ? (n ? 1)!? ? k ? k ?1 k ?1 k ?1 是一个整数. 但 k 是偶数, 所以 k+1 是奇数,因此 是奇数. 又 ? ? ? ? 1 ,所以 ? ? ? ? 2 ? p p p ? p? ? n ? n ? ? p? ? k ? ? (n ? 1)!? ( p ? 1)! 是偶数.如果 n = p, 则 k = 是偶数,所以 k+1 是奇数. 由威尔逊定理 k(p+1) = ? p? ? ? 2 ? p ?1 ? ? ?n ?n?
-1(mod p),所以

? k ? ? (n ? 1)!? ? k ? k ? 1 k ?1 是一个奇数,所以 ? ? ? ? 2 ? = ? ? ? p ? 1 是偶数.综上,原命题成立 p ? p? ? n ? n ? ? p?

评注 当 n 和 n+1 之一是素数时,由 (n ? 1)!我们联想到威尔逊定理。 练习 7. 设 {an },{bn } 定义如下: a0 ? 1, a1 ? 1, an?1 ? an ? 2an?1 , b0 ? 1, b1 ? 7, bn?1 ? 2bn ? 3bn?1 (n ? 1,2,...)

? 3bn?1 (n ? 1,2,...),证明:除“1”以外这两个数列没有其它相同的项。
证明: a0 ? 1, a1 ? 1, a2 ? 3, a3 ? 5, a5 ? 11... , b0 ? 1, b1 ? 7, b2 ? 17, b3 ? 55, b4 ? 161... 下面证明:
7

a2n?1 ? 5(mod8), a2n?2 ? 3(mod8) ;b2n?1 ? 7(mod8),b2n?2 ? 1(mod8) ,其中 n 为正整数。初值易验证,
假设 a2k ?1 ? 5(mod8), a2k ?2 ? 3(mod8) , 则 a2k ?3 ? a2k ?2 ? 2a2k ?1 ? 3 ? 2 ? 5 ? 5( m o d

8) ,a2k ?4 ? a2k ?3 ? 2a2k ?2 ? 5

a2k ?4 ? a2k ?3 ? 2a2k ?2 ? 5 ? 2 ? 3 ? 3(mod8) ,可知 n ? k ? 1 时结论成立。同理可证 {bn } 。因而原命题成立。 (a ? 1) n ? a n 练习 8. 求所有的正整数对 ( a, n) 使得 是整数。 n 证明:若 a 为任意正整数,则 (a,1) 显然是原问题的解,下面我们证明原问题没有其他解。若 n ? 2 ,
n n 易 知 (a, n) ? (a, n ? 1) ? 1 , 不 妨 设 p 为 n 的 最 小 素 因 子 , 则 p ( a ? 1) ? a , 又 由 费 马 小 定 理

p ( a ? 1) p ?1 ? a p ?1 , 而 ( p ? 1, n) ? 1 , 由 裴 蜀 定 理 存 在 正 整 数 u , v , 使 u ( p ? 1) ? vn ? 1 。 则
vn p (a ? 1) u ( p ?1) ? a u ( p ?1) ? (a ? 1) vn?1 ? a vn?1 = (a ? 1)((a ? 1) vn ? a vn ) ? a vn , 所以 p a , 与 (a, n) ? 1矛盾。

所以没有其他的正整数解。

8