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

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


同余理论及其应用
基础知识 一. 定义 定义 1. 设 m 为正整数, 整数 a 和 b 之差可被 m 整除时, 称为 a 和 b 关于模 m 同余, 记作 a ? b(mod m). 定义 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) 为欧拉 函数。当 n 二. 定理 定理 1. a ? b(mod m). 的必要充分条件是 a 和 b 被 m 除的余数相等。 定 理 2. I. a ? a(mod m); II. 若 a ? b(mod m), 则 b ? a(mod m); III. 若 a ? b(mod m), b ? c(mod m), 则
? ? ? p1 1 p2 2 ? p? s 时,有 ? (n) ? n(1 ? s

1 1 1 )(1 ? )...(1 ? ) p1 p2 ps

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

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

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

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

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

m ? 1) f ,则它们 f

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

? 1(mod m)
1

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

p ?1

? 1m (o d

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

定理 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(mod 8) ,证明 p 必不能表作三个平方数之和。 分析 我们利用平方数模 8 的性质进行处理。
2 2 2 证明:设存在三个整数 a, b, c 使 p ? a ? b ? c . 其中 a, b, c 或为偶数,或为奇数。因此下式 a ? 0(mod 8),
2

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

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

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

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

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

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

1

3

1

3

2

4

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

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

? n(mod 13) , n 7 ? n(mod 7) , n 5 ? n(mod 5) ,

n 3 ? n(mod 3) , n 2 ? n(mod 2) ,而 n13 ? n ? (n 7 ? n)( n 6 ? 1) ? (n 5 ? n)( n 8 ? n 4 ? 1) ? (n 3 ? n)( n10 ? n 8 ? n 6 ? n 4 ?

n 3 ? n)( n10 ? n 8 ? 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 ? ? (k 2 p ?1 ? ( p ? k ) 2 p ?1 ) , 由二项式定理:( p ? k ) 2 p ?1 ? p 2 p ?1 ? ... ? C 2 p ?1 p 2

?k

p ?1

2 p ?1

?

p ?1

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

k ?1

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

2 p ?2 ? mp 2 ? 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 ? mp 2 ? p ? ? p(mod p 2 ) 所以 ? k 2 p ?1 ? ? (? p) ? ( )( ? p)(mod p 2 ) ? p ? p ? p 2 ? p( p ? 1) (mod p 2 ). 2 k ?1 2 2 k ?1 ? p2 p( p ? 1) 2 2 ?p ? (mod p ). 所以,原结论成立。 2 2

评注 二项式定理也是处理数论问题的重要工具。 三. 同余与不定方程 例 5. (2004 年韩国数学竞赛)证明:方程 3 y ? x ? x 没有正整数解。
2 4

分析 我们选择适当的模对 x 进行分类处理问题。 证明:(1)当 x ? 3a ? 1(a ? N ) 时, x ? x ? 2(mod 3)
4 4 2

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

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

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

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

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 *) 则 a(3a ? 1)(3a 2 ? 3a ? 1) ? 3c 2 , 3 | a. 令 a ? 3b(b ? N *) , b(9b ? 1)( 27b 2 ? 9b ? 1) ? c 2 与 则 (2) 类似, ? ? b ? t2 (t , m ? N *) 则 9t 2 ? 1 ? m 2 ,即 (3t ? m)(3t ? m) ? 1 b,9b ? 1,27b 2 ? 9b ? 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 是质数的条件。 解:若 x ? y ,则 xy ? 19 无整数解;若 x ? y ,则 y ? x ? xy ? 19. 由于 x, y 是质数,由费马小
2 x y 2

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

①,再由费

马小定理

y x ? y ( m o d) x

? y x ? x y ? xy 2 ? y(mod x). 即 y ? 19(mod x) 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 无解; 若 y ? 19 , 4. 则当 y ? 17 时:17 x ? x17 ? x ? 17 2 ? 19. 易知:x ? 17 时,17 x ? x17 ? 0 , ?y ? x, 无解,? 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 ? 23 ? 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) ,使
2 这个 i 决不能等于 a, 事实上, 如果 i ? a , 则有 a ? 1(mod p) , 从而就有 (a ? 1)(a ? 1) ? 0(mod p) ia ? 1(mod p) 。

? 1)(a ? 1) ? 0(mod p) 。由于 p 是素数,且 p ? 2 ,故 a ? 1 ? 0(mod p) 或 a ? 1 ? 0(mod p) ,两者必居其一。但 |
1 ? a ? p ? 1 ,即 0 ? a ? 1 ? p, 2 ? a ? 1 ? p 。所以不可能有 a ? 1 ? 0(mod p) 及 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 ? p ? 1. 再次可以证明 i ? 1. 否则就有 ia ? a ? 1(mod p) ,但这与 1 ? a ? p ? 1 矛盾。这样就证明了数列 ? ?
②中必有一数 ia,有 ia ? 1(mod p) ,而又 i ? 1. i ? p ? 1. i ? a ,故 i 必为①中一数且与 a 相异。此外, ? ? ? 如果①中有两数 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 的结论。

1 证明:对任意 S ? ? ,2,..., p ? 1?,都存在唯一的 S
时, S
?1

?1

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

? 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 ? 1(mod p) 有且仅有两解 x ? ?1(mod p) ,所以除了 1, ? 1 和自己配对
2

外,其余 p ? 3 个数恰可配成 评注 本题即威尔逊定理。 五. 同余与其他

p?2 p?3 对。? ? ? 1(mod p ). 2 i?2

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

例 9. 已知 a1 ? 1, a 2 ? 2, a n ? 2 ? ?

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

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

证明:若某一个 a k ? 0 ,则对任意正整数 m 有 a k ? 0(mod m) ,因此,我们只要找到一个 m,对任 何一个 n 均有 a k ? 0(mo dm) 即可, a1 ? 1(mo d4) ?

4 a 2 ? 2( mo d ) a3 ? 3( mo d ) 。设 n ? k 时, 4

a3k ? 2 ? 1(mo d4) ,a3k ?1 ? 2(mod 4) ,a3k ? 3(mod 4) , n ? k ? 1时,a3k ?1 ? 5a3k ? 3a3k ?1 ? 1(mod 4) 则 a3k ? 2 ? a3k ?1 ? a3k ? 2( mo d ) , 3k ?3 ? 5a3k ? 2 ? 3a3k ?1 ? 3(mod 4) , 4 a 因此对一切 n 均有 a k ? 0(mod 4) , ?
从而原命题成立。 评注 同余是处理此类问题的有效方法之一。 例 10. (1996 年保加利亚)求所有的质数 p, q ,使得 pq 整除 (5 ? 2 )(5 ? 2 )
p p q 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

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

p 3 ? 2 vp

, 矛盾。 所以 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 ? x 2 ? ... ? x s ,
2 2 2

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

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

5

评注 对于某些问题,常常需要多次选择不同的模进行同余处理。
25

练习 2. 求出大于 1 的整数 n 的个数,使得对任意的整数 a ,都有 n | a 分析 联想例 4,猜想 n 的最大值为 2730。 解:设满足条件的正整数组成集合 S,若 n | a
25

?a

? a , m | a 25 ? a ,则 [m, n] | a 25 ? a ,因此 S 中全
25

部数的最小公倍数也属于 S ,即 S 中的最大数是其余每个数的倍数。 m | a

? 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. 2
340

? 1(mod 341) 但 341 ? 11 ?13 为合数,则称 341 是伪质数,证明:伪质数有无穷多个。

分析 我们想办法构造出具体的表达或递推关系。 证明: 已知 341 为伪质数, 假设 m 是伪质数, 下面证明 2 m ? 1 是伪质数, 首先, m ? pq , 设 其中 p, q 为大于 1 的整数, 2 ? 1 ? 2 则
m pq

含有因子 2 p ? 1 , 并且 1 ? 2 p ? 1 ? 2 m ? 1, 所以 2 m ? 1 ? 1 ? (2 p ) q ? 1 ,
m

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

m ?1

22

m

?2

? 1 ? (2 2

m ?1

?1

? 1)( 2 2

m ?1

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

?1) ?1

?1

? 1) , 而 2 2

m ?1

? 1 ? 22

m

?2

? 1 ? (2 2

m ?1

?1

?1

? 1 ? 2 ms ? 1 ? (2 m ) s ? 1 , 可 被 2 m ? 1 整 除 , 因 而

2( 2

m

?1) ?1

? 1(mod(2 m ? 1)) ,所以 2 m ? 1是伪质数,并且 2 m ?1 ? m 。由此可知伪质数有无穷多个。
3 3 3 2002

评注 利用递推关系构造是解决无穷解问题的重要构造方法。 练习 4. (第 43 届 IMO 预选题)求最小的正整数 n,使得: x1 ? x 2 ? ... ? x n ? 2002 分析 我们先估计出 n 的值,在构造出一组解。 解:2002 ? 4(mod 9) ,4 ? 1(mod 9) ,2002 ? 667 ? 3 ? 1 , 所以 2002
3
3 3 3 3 3 3

有整数解。

2002

? 4 2002 ? 4(mod 9) 又

3 3 x 3 ? 0,?1(mod 9) 其中 x ? Z , 于是 x1 , x1 ? x 2 , x1 ? x 2 ? x3 ? 4(mod 9) , 由于 2002 ? 10 ? 10 ? 1 ? 1 ?
667

? 10 3 ? 10 3 ? 1 ? 1 ,则 2002 2002 ? 2002 ? (2002 667 ) 3 ? (10 ? 2002
所以 n ? 4 。

) 3 ? (10 ? 2002

667

) 3 ? (2002

667

) 3 ? (2002 667 ) 3

评注 选择适当的模,利用同余进行估计是重要的方法之一。 练习 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)!? 2 ? 是偶数. 我们最后考虑 n+1 = p ?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 ? 1 ,所以 ? ? ? ? 2 是一个整数. 但 k 是偶数, 所以 k+1 是奇数,因此 是奇数. 又 ? ? ? ? p p p ? p? ? n ? n ? ? p? ? k ? ? (n ? 1)!? ( p ? 1)! ? p? ? ? 2 ? 是偶数.如果 n = p, 则 k = p ? 1 是偶数,所以 k+1 是奇数. 由威尔逊定理 k(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. 设 {a n }, {bn } 定义如下: a0 ? 1, a1 ? 1, a n ?1 ? a n ? 2a n ?1 , b0 ? 1, b1 ? 7, bn ?1 ? 2bn ? 3bn ?1 (n ? 1,2,...)

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

a2 n?1 ? 5(mod 8), a2 n? 2 ? 3(mod 8) ;b2 n?1 ? 7(mod 8), b2 n? 2 ? 1(mod 8) ,其中 n 为正整数。初值易验证, (o d 假设 a 2 k ?1 ? 5(mod 8), a 2 k ? 2 ? 3(mod 8) , a 2 k ?3 ? a 2 k ? 2 ? 2a 2 k ?1 ? 3 ? 2 ? 5 ? 5m 则

8) ,a2 k ? 4 ? a2 k ?3 ? 2a2 k ? 2 ? 5

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

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


相关文章:
高中数学竞赛专题讲座---同余理论及其应用(一)
高中数学竞赛专题讲座---同余理论及其应用(一)_学科竞赛_高中教育_教育专区。同余理论及其应用基础知识 一. 定义 定义 1. 设 m 为正整数, 整数 a 和 b 之差...
高中数学竞赛专题讲座---同余理论及其应用(二)
高中数学竞赛专题讲座---同余理论及其应用(二)_学科竞赛_高中教育_教育专区。数论定理一. 知识要点 1. 欧拉定理和费尔马小定理 缩系的定义:设 m 为正整数,一...
同余理论在数学竞赛中的运用
高中数学竞赛专题讲座--... 8页 免费同​余​理​论​在​数​学...下面, 本文重点论述一下同余理论在数学竞赛 中的运用。首先,先介绍一下同余的...
高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)
高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)_学科竞赛_高中教育_教育专区。同余的概念与应用概念与性质 1. 定义: 若整数 a,b 被整数 m(m≥1)...
高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题)
同余理论在数学竞赛中的应... 2页 免费 高中数学竞赛专题讲座---同... 11页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此...
同余理论在中学数学竞赛中的应用
高中数学竞赛专题讲座---同... 8页 免费如要投诉违规内容,请到百度文库投诉中心...同余理论在中学数学竞赛中的应用数学与统计学院、数学与应用数学、0701 班,湖北,...
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_教育专区。数学归纳法数学归纳法是用于证明与正整数 n 有关的数学命题的正确性的一种...
高中数学竞赛专题讲座解析几何
高中数学竞赛专题讲座解析几何。高中数学竞赛专题讲座——解析几何一、选择题部分 1. (集训试题)过椭圆 C: x2 y2 ? ? 1 上任一点 P,作椭圆 C 右准线...
高中数学竞赛专题讲座解析几何
高中数学竞赛专题讲座解析几何。高中数学竞赛专题讲座——解析几何一、选择题部分 1.(集训试题)过椭圆 C: x2 y2 ? ? 1 上任一点 P,作椭圆 C 右准线...
更多相关标签:
同余问题理论 | 同余理论 | 整数与同余理论 | 高中数学竞赛专题讲座 | 初中数学竞赛专题讲座 | 教育理论专题讲座 | 同余定理 | 同余方程 |