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

第三讲 同余系列竞赛


Http://www.fhedu.c 【高中数学奥赛金牌之路精华教案】数学奥赛辅导

第三讲 同余

知识、方法、技能
同余是数论中的重要概念,同余理论是研究整数问题的重要工作之一.本讲介绍同余的 基本概念,剩余类和完全剩余系,同余方程,整数模的阶和中国剩余定理. Ⅰ.基本概念 定义一:设 m 是一个给定的正整数.如果两个整数 a

、b 用 m 除所得的余数相同,则称 a、b 对模 m 同余,记为 a≡b(modm);否则,记为 a≡b(modm). 例如,15≡7(mod4),-23≡12(mod7). 同余有如下两种等价定义法: 定义一* 若 m|a-b,则称 a、b 对模 m 同余. 定义一**若 a=b+mt(t∈Z),则称 a、b 对模 m 同余. 同余的基本性质: (1) a ? 0(mod m) ? m | a. (2) a ? a(mod m)(反身性)

a ? b(mod m) ? b ? a (mod m)( 对称性) a ? b(mod m) ? ? ? a ? c (mod m)( 传递性) b ? c (mod m) ?
(3)若 a ? b(mod m), c ? d (mod m), 则 ① a ? c ? b ? d (mod m); ② ac ? bd (mod m). ( 4 ) 若

ai ? bi (mod m), i ? 0,1,2,?, n.则, a n x n ? ? ? a1 x ? a0 ? bn x n ? ? ? b1 x ? b0 (mod m). 特别地,设

f ( x) ? a n x n ? ? ? a1 x ? a0 (ai ? Z ), 若a ? b(mod m) ,则 f (a) ? f (b)(mod m).
( 5 ) 若 ac ? bc(mod m), 则a ? b(mod

m ). 特 别 地 , 又 若 ( c,m ) =1 , 则 (m, c)

a ? b(mod m).
【证明】 m | c(a ? b), 这等价于 因

a b m c (a,b) d ? ( , ) =1 = | (a ? b). 又因若 (m, c) (m, c) d d

(d≠0)及 b|ac,且(b,c)=1 ? b | a,
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 1

Mail:admin@fhedu.cn

Http://www.fhedu.c 从而有

m | (a ? b). (m, c)

这个性质说明同余式两边的同一非零因数,不能像等式那样“约去”,只有当这非零 因数与模互质时,才可“约去”. (6) a ? b(mod m), 而 d | m(d ? 0), 则a ? b(mod d ). (7)设 a ? b(mod m), ①若 c>0,则 ac ? bc(mod mc); ②d 为 a、b、m 的任一公约数,则

a b m ? (mod ). d d d

(8)若 a ? b(mod m1 ), a ? b(mod m2 )且(m1 , m2 ) ? 1, 则a ? b(mod m1m2 ). (9)若 a ? b(mod m), 则(a, m) ? (b, m). Ⅱ.剩余类和完全剩余系 若按对某一模 m 的余数进行分类,就可以引入所谓的剩余类和完全剩余系的概念. 定义二:设 m∈N*,把全体整数按其对模 m 的余数 r(0?r?m-1)归于一类,记为 kr,每一类 kr(r=0,1,?,m-1)均称模 m 的剩余类(又叫同余类).同一类中任一数称为该 类中另一数的剩余. 剩余类 kr 是数集 k r ? ?qm ? r | m是模, r是余数, q ? Z ?, 也即k r ? ?a | a ? Z且a ? r (mod m)? , 它是一个公差为 m 的(双边无穷)等差数列. 根据定义,剩余类具有如下性质: (1) Z ? k 0 ? k1 ? k 2 ? ? k m?1 , 而k i ? k j ? ? (i ? j ); (2)对任一数 n∈Z,有惟一的 r0 使n ? k r0 ; (3)对任意的 a,b∈Z,a,b ? k r ? a ? b(mod m). 定义三:设 k 0 , k1 , ?, k m ?1 是模 m 的(全部)剩余类.从每个 kr 中任取一个数 ar,这 m 个 数 a 0 , a1 , ?, a m ?1 组成的一个组称为模 m 的一个完全剩余系,简称完系. 例如,取 m=4,则有 k 0 ? ? ,?8,?4,0,4,8??, k1 ? ? ,?7,?3,1,5,9,?? ,k2={?,-6,-2, ? ? 2,6,10,?},k3={?,-5,-1,3,7,11,?}.数组 0,1,2,3;-8,5,2,-1 等 等都是模的 4 的一个完全剩余系. 显然,模 m 的完全剩余系有无穷多个.但最常用的是下面两种: (1)非负数最小完全剩余系:0,1,2,?,m-1; (2)绝对值最小完全剩余系:它随 m 的奇偶性不同而略有区别.
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 2 Mail:admin@fhedu.cn

Http://www.fhedu.c 当 m ? 2k ? 1 , 为 ? k ,?(k ? 1), ?,?1,0,1,?, (k ? 1), k. (对称式) 时 当 m ? 2k时, 为 ? (k ? 1),?(k ? 2), ?,?1,0,1, (k ? 1), k.或 ? k ,?(k ? 1), ?,?1,0,1,?, (k ? 1). 由定义不难得到如下判别完全剩余系的方法: 定理一:m 个整数 a1 , a 2 ,?, a m 是模 m 的一个完系 ? 当i ? j时, ai ≡ a j (mod m) 定理二: (b,m) c 为任意整数.若 a1 , a 2 ,?, an 为一个完系, ba1 ? c, ba2 ? c,?, bam ? c 设 =1, 则 也是模 m 的一个完全剩余系. 特别地,任意 m 个连续整数构成模 m 的一个完全剩余系. 【证明】只需证明:当 i ? j时, bai ? c ? ba j ? c(mod m). 而这可用反证法得证.下略. 设 m 为一正整数,由于在 0,1,?,m-1 中与 m 互质的数的个数是由 m 惟一确定的 一个正整数,因此,可给出如下定义. 定义四:m 为一正整数,把 0,1,?,m-1 与 m 互质的数的个数叫做 m 的欧拉函数, 记为 ? (m). 显然, ? (m) 的定义域是正整数 N*,前 n 个值为:

? (1) ? 0, ? (2) ? 1, ? (3) ? 2, ? (4) ? 2, ? (5) ? 4, ? (6) ? 2, ? (7) ? 6, ?, 当 m=p 为质数
时, ? ( p) ? p ? 1. 设 k 是模的一个剩余类.若 a、b∈k,则 a ? b(mod m). 于是由性质 9 知,(a,m)=(b,m). 因此,若(a,m)=1,则 k 中的任一数均与 m 互质.这样,又可给出如下定义. 定义五:如果一个模 m 的剩余类 kr 中任一数与 m 互质,则称 kr 是与模 m 互质的剩余 类;在与模 m 互质的每个剩余类中任取一个数(共 ? (m) 个)所组成的数组,称为模 m 的 一个简化剩余系. 例如,取 m=6,在模 6 的六个剩余类中,

k1 ? ? ,?11,?5,1,7,13,??, ?
k 5 ? ? ,?7,?1,5,11,17,?? 是与模 6 互质的剩余类.数组 1,5;7,-7;1,-1;等等 ?
都是模 6 的简化剩余类. 由此定义,不难得到: 定理三: a1 , a 2 ,?, a? ( m ) 是模 m 的简化剩余系 ? (ai , m) ? 1, 且ai ? a j (mod m)(i ? j, i, j ? 1,2,?? (m)). 定理四:在模 m 的一个完全剩余系中,取出所有与 m 互质的数组成的数组,就是一个 模 m 的简化剩余系.
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 3 Mail:admin@fhedu.cn

Http://www.fhedu.c 这两个定理,前者是简化剩余系的判别方法,后者是它的构造方法.显然,模 m 的简化 剩余系有无穷多个,但常用的是“最小简化剩余系”,即由 1,2,?,m-1 中与 m 互质 的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理. 定理五:设 a1 , a 2 ,?, a? ( m ) 是模 m 的简化剩余系.若(k,m)=1,则 ka1 , ka2 , ?, ka? ( m ) 也是 模 m 的简化剩余系. 下面介绍两个有关欧拉函数的重要结论.其证明略. 定理六:(欧拉定理)若(a,m)=1,则 a
? ( m)

? 1(mod m)
p ?1

特别地,(费马小定理)若 m=p 为质数,p a,则 a

? 1(mod p).

定理七:(威尔逊定理)设 p 素数,则(p-1)! ? ?1(mod p). 定理八:(欧拉函数值计算公式)令 m 的标准分解式为
? ? ? m ? p1 1 p 2 2 ? p k k ,
k



? (m) ? m? (1 ?
i ?1

1 ). pi

例如,30=2·3·5,则 ? (30) ? 30(1 ? )(1 ? )(1 ? ) ? 8. 读者应认识到:由于任何整数都属于模 m 的某一剩余类,所以,在研究某些整数性质 时,选取适当的(模)m,然后在模 m 的每个剩余类中取一个“代表数”(即组成一个完 全剩余系),当弄清了这些代表数的性质后,就可弄清对应的剩余类中所有数的性质,进而 弄清全体整数的性质,这就是引入剩余类和完全剩余系的目的. Ⅲ.同余方程 设 f ( x) ? a n x ? a n ?1 x
n n ?1

1 2

1 3

1 5

? ? ? a1 x ? a0为x 的整系数多项式.类似于多项式和代数方

程式的有关定义,我们有 定义六:同余式 f ( x) ? 0(mod m), a n ? 0(mod m) 叫做一元 n 次同余方程.例如,

9 x 7 ? 3x 5 ? 5 x 2 ? 3 ? 0(mod 3) 是七次同余方程.
定义七: c 使得 f (c) ? 0(mod m)成立, 则x ? c(mod m) 叫做同余方程 f ( x) ? 0(mod m) 若 的一个解. 显然,同余方程的解是一些剩余类,而不仅是一个或 n 个类.例如, x ? 1(mod 5),

x ? 4(mod 5) 都是二次同余方程 x 2 ? 1(mod 5) 的解.
1.一次同余方程
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 4

Mail:admin@fhedu.cn

Http://www.fhedu.c

ax ? b(mod m) (其中 m a)称为一次同余方程.关于它的解,有如下共知的结论:
定理九:若(a,m)=1,则 ax ? b(mod m) 有一个解. 定理十:若(a,m)=d>1,d b,则 ax ? b(mod m) 无解,其中 a ? 0(mod m) . 定理十一: (a,m) 若 =d>1, d|b, ax ? b( od m) 有 d 个解.并且, ?x ? ? (mod m1 ) 则 若 m 的一个解为 x ? r (mod m1 ), 则 d 个解为: x ? r ? km (mod m), k ? 0,1,?, d ? 1 , 1 其中 ? ?

a b m , ? ? , m1 ? . d d d
(*)

下面介绍一次同余方程

ax ? b(mod m), (a, m) ? 1
的解法.

【解法 1】因(a,m)=1,则存在二数 s,t,使得 as+mt=1,即 as ? 1(mod m) ,由此有

asx ? bs(mod m), 于是x ? bs(mod m) 为(*)的解.
【解法 2】先把(*)变形成 x ?

b b (mod m)( 仅只是形式上的记号),然后用与 m 互 a a

质的数陆续乘右端的分子分母,直至把分母绝对值变成 1(通过分子分母各对模 m 取余数) 而得到解. 【解法 3】 得用欧拉定理.因 a ? ( m) ? 1(mod m),由ax ? b(mod m)可得a ? ( m) x ? b ? a ? ( m)?1 (mod m), 从而有解

x ? b ? a ? ( m)?1 (mod m).

2.一次同余方程组 定义八:若数 r 同时满足 n 个同余方程: f k ( x) ? 0(mod mk ), k ? 1,2,?, n.则r 叫做这 n 个同余方程组成的同余方程组的解. 定理十二:对同余方程组

? x ? c1 (mod m1 ), ? ? x ? c 2 (mod m 2 ).
记 (m1 , m2 ) ? d , [m1 , m2 ] ? M . ①若 d c1 ? c2 ,则此同余方程组无解; ②若 d | c1 ? c2 ,则此同余方程组有对模 M 的一类剩余解. Ⅳ.模 m 的阶和中国剩余定理
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 5 Mail:admin@fhedu.cn

Http://www.fhedu.c (1)模 m 的阶 定义九:设 m>1 是一个固定的整数,a 是与 m 互素的整数,则存在整数 k,1?k<m, 使得 a ? 1(mod m) .我们将具有这一性质的最小正整数(仍记为 k)称为 a 模 m 的阶.
k

a 模 m 的阶具有如下性质: ① 设 (a, m) ? 1, k是a模m 的 阶 , u,? 是 任 意 整 数 , 则 a u ? a v (mod m) 的 充 要 条 件 是 u ? ? ( mo d ) . k 特别地, a ? 1(mod m) 的充分必要条件是 k|u.
u

【简证】充分性显然. 必 要 性 . 设 u ? ? , 记l ? u ? ? , 则由a ? a (mod m)及(a, m) ? 1易知a 1(mod m). 用
u l

?

带余除法,l ? kq ? r , 这里0 ? r ? k , 故a

kq

? a r ? 1(mod m), 即a r ? 1(mod m).由0 ? r ? k

及 k 的定义知,必须 r=0,所以 u ? r (mod k ). ②设 (a, m) ? 2, a 模 m 的阶为 k,则数列 a, a , a ,?, 模 m 是周期的,且最小正周期
2 3

是 k,而 k 个数 a, a , ? , a 模 m 互不同余. ③设 (a, m) ? 1, 则a 模 m 的阶整除欧拉函数 ? (m). 特别地,若 m 是素数 p,则 a 模 p 的阶整除 p-1. (2)中国剩余定理(即孙子定理) 设 n ? 2, m1 , m2 ,?, mn 是两两互质的正整数, M= 记 同余方程组

2

k

?m ,M
i i ?1

n

i

?

M (i ? 1,2, ?, n) 则 mi

x ? ci (mod mi )(i ? 1,2,?, n)

有且只有解

x ? ? M i? i ci (mod M ).
i ?1

n

(△)

其中 M i? i ? 1(mod mi ), i ? 1,2,?, n.

(△△)

( 【证明】 (mi , m j ) ? 1(i ? j ) 知, M i , m j ) ? 1 , 由 因此每一个同余方程 M iy ? 1(mod mi )
(i=1,2,?n)都有解,于是必存在 ? i , 使得M i? i ? 1(mod m).又因M ? mi M i , mi | M i (i ? j ), 所 以 对 模

mi (i ? 1,2,?, n)有M 1?1c1 ? ? ? M i? i ci ? ? ? M n? n cn ? M i? i ci ? ci (mod mi ). 故(△
△)是(△)的解.
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 6 Mail:admin@fhedu.cn

Http://www.fhedu.c 若 x1 , x 2 是适合 (△) 的任意两个解, x1 ? x 2 (mod mi ), i ? 1,2, ? , n, 因(mi , m j ) ? 1(i ? j ). 则 故 x1 ? x2 (mod m1 m2 ? mn ), 即x1 ? x2 (mod M ), 因此,(△△)是(△)的惟一解.

赛题精讲
例 1:数 1978n 与 1978m 的最末三位数相等,试求正整数 m 和 n,使得 n+m 取最小值, 这里 n ? m ? 1. (第 20 届 IMO 试 题) 【解】由已知 1978 ? 1078 (mod 1000 ), 而 1000=8×125,所以
n m n m 1 9 7 8 ? 1 0 7 8 ( m o 8) d

① ②


1978 n ? 1078 m (mod 125)

因 n ? m ? 1 ,且(1978m,125)=1,则由②式知 1978n m≡1(mod125)③ 又直接验证知,1978 的各次方幂的个位数字是以 8、4、2、6 循环出现的,所以只有 n -m 为 4 的倍数时,③式才能成立,因而可令 n-m=4k.由于. n+m=( n-m)+2m=4k+2m, 因而只需确定出 k 和 m 的最小值. 4 先确定 k 的最小值: 因为 19784= (79×25+3)≡34≡1 (mod5) 19784≡34≡1 , (mod25) . 故可令 19784=5t+1, 5 t, 而 从而 0≡1978n
-m

k -1=19784k-1= (5k+1) -1≡

k (k ? 1) ? (5t ) 2 2

+ k ? 5t (mod 125 ) ,显然,使上式成立的 k 的最小值为 25. 再确定 m 的最小值:因 1978≡2(mod8),则由①式知, 2 ? 2 (mod 8)
n m



由于 n ? m ? 1, ④式显然对 m=1,2 不成立,从而 m 的最小值为 3. 故合于题设条件的 n+m 的最小值为 106. 【评述】比例中我们用了这样一个结论:1978 的各次方幂的个位数字是以 8,4,2,6 循环出现,即,当 r=1,2,3,4 时, 1978
p

? 1978 4 q ?r ? 8,4,2,6(mod 10). 这种现象在数

学上称为“模同期现象”.一般地,我们有如下定义: 整数列 ?x n ? 各项除以 m(m?2,m∈N*)后的余数 a n 组成数列 ?a n ?.若 ?a n ?是一个周 期数列, 则称 ?x n ? 是关于模 m 的周期数列, 简称模 m 周期数列.满足 a n ?T ? a n (或 a n ?T ? x n (modm))的最小正整数 T 称为它的周期. 例如,(1) 1978

?

n

?是模 10 周期数列,周期为 4;(2)自然数列{n}是一个模 m(m
联系电话:025-83657815 7

?2,m∈N*)周期数列,周期为 m;(3)任何一个整数等差数列都是一个模 m(m?2, m∈N*)周期数列,周期为 m.
网站地址:南京市湖南路 1 号 B 座 808 室 Mail:admin@fhedu.cn

Http://www.fhedu.c 例 2:设 a 是方程 x ? 3x ? 1 ? 0 的最大正根,求证:17 可以整除[a1788]与[a1988].其中
3 2

[x]表示不超过 x 的最大整数.

(第 29 届 IMO 预选题)

【证明】根据如下符号表可知,若设三根依次为 ? ? ? ? a , 则 ?1 ? ? ? ?

1 1 , ? ? ? 1, 2 2
-1 - -

x f(x)符号

1 2

1 2
+

1 -

2 3


3 +

+

2 2 ? a,由于f (?? ) ? ?2? 3 ? (? 3?2? 2 ? 1) ? ?2? 3 ? 0, 于是 ? ? ? ? , | ? |? ? .

另一方面,由韦达定理知,

? 2 ? ? 2 ? (? ? ? ) 2 ? 2?? ? (3 ? a) 2 ?

2 2 ? 6a 2 ? a 3 ? 2a 3 ? a 3 ?9? ?9? ? 1 ? (8 ? a 2 ) a a a

? a 2 ? (2 2 ) 2 ? 8,?? 2 ? ? 2 ? 1.
为了估计[ a
1788

]、[ a

1988

],先一般考察[an],为此定义:

u n ? ? n ? ? n ? a n .( n ? 0,1,2,?)
直接计算可知: 0 ? 3, u1 ? 2 ? ? ? a ? 3.u 2 ? ? 2 ? ? 2 ? a 2 ? 9,以及u n?3 ? 3u n? 2 ? n(n ? 0). u 又 因 0 ? ? n ? ? n ? 1(?| ? |? ? ,即? n ? ? n ? 0, 又? ? ? ? 3 ? ? ? 2 ? 2 2 ? 1, 当

n?2





? n ? ? n ?| ? | n ? ? n ? ? 2 ? ? 2 ? 1), 则a n ? u n ? (? n ? ? n ) ? u n ? 1 ? [1 ? (? n ? ? n )].
?[a n ] ? u n ? 1.( n ? 1,2,?)
由此知,命题变为证明: u1788 ? 1和u1988 ? 1 能被 17 整除. 现考察 ?u n ? 在模 17 的意义下的情况:

u 0 ? 3, u1 ? 3, u 2 ? 9,u 3 ? 7, u 4 ? 1, u5 ? 11, u 6 ? 9,u 7 ? 9, u8 ? 16, u9 ? 5, u10 ? 6,u 11? 2,
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 8 Mail:admin@fhedu.cn

Http://www.fhedu.c

u12 ? 1, u13 ? 14, u14 ? 6,u 15 ? 0, u16 ? 3, u17 ? 3, u18 ? 9,??
可见,在模 17 意义下, ?u n ? 是 16 为周期的模周期数列,即 u n ?16 ? u n (mod 17 ). 由于 1788 ? 12(mod 16),1988 ? 4(mod 16), 故u1788 ? u12 ? 1(mod 17 ), u1988 ? u 4 ? 1(mod 17 ), 故

u 1788?1 ? 0, u1988 ? 1 ? 0(mod 17 ). 命题得证.
例 3:求八个整数 n1 , n2 ,?, n8 满足:对每个整数 k(-1985<k<1985),有八个整数 a1,a2,?,a8∈{-1,0,1},使得 k ? a1 n1 ? a 2 n2 ? ? ? a8 n8 . 题) 【解】令数集 G ? ?k | k ? a1 ? a 2 ? 3 ? a3 ? 32 ? ? ? a n?1 ? 3n , ai ? {?1,0,1}, i ? 1,2,?, n ? 1? . (第 26 届 IMO 预选

显然

m a x ? 1 ? 3 ? 32 ? ? ? 3n ? G

3n ?1 ? 1 2



H,

mixG ? 1 ? 3 ? 32 ? ? ? 3n ? ? H .
且 G 中的元素个数有 3
n ?1

? 2H ? 1 个.又因 G 中任意两数之差的绝对值不超过 2H,所以 G

中的数对模 2H+1 不同余.因此,G 的元素恰好是模 2H+1 的一个绝对值最小的完系,于是, 凡满足 ? H ? k ? H 的任意整数都属于 G, 且可惟一地表示为: 1 ? a 2 ? 3 ? a3 ? 32 ? ? ? a n?1 ? 3n a 形式. 当 n=7 时,H=3280>1985,而 n=6 时,H=1043<1985.故 n1=1,n2=3,?,n8=37 为所求. 例 4:设 n 为正整数,整数 k 与 n 互质,且 0<k<n.令 M={1,2,?,n-1},给 M 中每 个数染上黑、白两种颜色中的一种,染法如下:(i)对 M 中每个 i,i 与 n-i 同色;(ii) 对 M 中每个 i,i≠k,i 与|k-i|同色.求证:M 中所有的数必为同色. (第 26 届 IMO 试 题) 【证明】因 (k , n) ? 1, 又 0,1,?n-1 是模 n 的一个完全剩余系,所以 0,k,2k,?, (n-1) 也是模 n 的一个完全剩余系.若设 jk ? r j (mod n)(其中 ? r j ? n ? 1, j ? 1,2,?, n ? 1), k 1 则 M= {r1 , r2 ,?, rn ?1 }. 下只需证 r j ?1与r j (1 ? j ? n ? 2). 因为,若如此,当 r1 的颜色确定后, M 中所有都与 r1 同色. 由于 ( j ? 1)k ? r j ?1 (mod n), 则r j ? k ? r j ?1 (mod n) ,因此,

网站地址:南京市湖南路 1 号 B 座 808 室

联系电话:025-83657815

9

Mail:admin@fhedu.cn

Http://www.fhedu.c ( 1 ) 若 r j ? k ? n,则r j ?1 ? r j ? k , 于 是 , 由 条 件 ( i ) 知 ,

(ii) 知,k ? r j ?1与 | k ? r j ?1 ? k |? r j ?1 同色, k ? r j ?1 ? n ? r j 与n ? (n ? r j ) ? r j 同色.又由条件 故 r j ?1与r j 同色. 综上所述可知, r j ?1与r j 同色.命题得证. 例 5:设 a 和 m 都是正整数,a>1.证明: m | ? (a ? 1).
m

【证明】实上,显然 a与a ? 1 互素,且 a模a ? 1 的阶是 m,所以由模阶的性质③导
m m

出 m | ? (a ? 1).
m

例 6:设 p 是奇素数,证明:2p-1 的任一素因了具有形式 2 px ? 1, x 是正整数. 【证明】设 q 是 2p-1 的任一素因子,则 q≠2.设 2 模 q 的阶是 k,则由 2 ? 1(mod q)
p

知 k|p, k=1 或 p 因 p 是素数, 故 ( 这是能确定阶 k 的主要因素) .显然 k≠1, 否则 2 ? 1(mod q),
1

这不可能,因此 k=p. 现在由费马小定理 2
q ?1

? 1(mod q) 推出 k | q ? 1,即p | q ? 1. 因 p、q 都是奇数,故 q-

1=2px(x 是个正整数),证毕. 例 7:设 m,a,b 都是正整数,m>1,则 m ? 1, m ? 1) ? m
a b a b ( a ,b )

? 1.
( a ,b )

【证明】记 d ? (m ? 1, m ? 1). 由于(a,b)|a 及(a,b)|b,易知 m

?1 | ma ?1及

m ( a ,b ) ? 1 | m b ? 1 ,故 m ( a ,b ) ? 1 | d ,
另一方面设 m 模 d 的阶是 k,则由

m a ? 1(mod d ), m b ? 1(mod d )
推出,k|a 及 k|b,故 k|(a,b).因此 m 综合两方面可知, d ? m
( a ,b )
( a ,b )

? 1(mod d ), 即d | m ( a ,b ) ? 1.

? 1. 证毕.

例 8: n, 是给定的整数, 设 k n>0, k n-1) 且( 是偶数.证明: 存在 x, y, 使得( x, n) ? ( y, n) ? 1, 是 x ? y ? k (mod n). 【证明】我们先证明,当 n 为素数幂 p 时结论成立.实际上,我们能证明,存在 x,y,
网站地址:南京市湖南路 1 号 B 座 808 室 联系电话:025-83657815 10
?

Mail:admin@fhedu.cn

Http://www.fhedu.c 使 p xy,且 x ? y ? k . 如 p=2, 则条件表明 k 为偶数, 可取 x ? 1, y ? k ? 1; 如p ? 2, 则x ? 1, y ? k ? 1或x ? 1, y ? k ? 2 中有一对满足要求. 一般情形下, n ? p1 1 ? p r r 是 n 的标准分解, 设 上面已证明, 对每个 p i , 均有整数 x i ,
? ?

y i ,使 pi xiyi,且 xi ? yi ? k (1,2,?, r ). 现在孙子定理表明,同余方程组
? x ? x1 (mod p1 1 ), ?, x ? xr (mod prar ) 有解 x,同样

? y ? y1 (mod p1 1 ), ?, y ? y r (mod prar )

也有解 y.现在易证 x,y 符合问题中的要求:因 pi xiyi,故 pi xy(i=1,?,r),于是(xy, n)=1.又 x ? y ? xi ? y i ? k (mod pi 1 )(i ? 1,?, r ), 故x ? y ? k (mod n). 例 9:设 n 为任意的正整数.证明:一定存在 n 个连续的正整数解,使其中任何一个都 不是质数的整数幂. (第 30 届 IMO 试题) 【证明】 2n 个两两不同的质数 p1 , p2 ,?, pn 和q1 , q2 ,?, qn . 同余方程组 x ? ?i(mod pi qi ), 取
?

i ? 1,2,?, n .由于 p1q1 , p2 q2 ,?, pn qn 两两互质,根据孙子定理必有解,取为正整数 N,
则 n 个连续正整数 N+1,N+2,?,N+n 都至少含有两个不同的质因数,因而它们中的任一 个都不是质数的整数幂.证毕.

网站地址:南京市湖南路 1 号 B 座 808 室

联系电话:025-83657815

11

Mail:admin@fhedu.cn


相关文章:
第三讲 同余
第三讲 同余_学科竞赛_高中教育_教育专区。高中竞赛初等数论选讲,共6讲初等代数选讲---第三讲 第三讲 同余 同余的性质应用非常广泛,在处理某些整除性、进位制、...
第3讲同余
关键词:数学竞赛数论 同系列文档 第1讲整除 第2讲最大公约数与最小公倍......第三讲 第三讲 同余一、基础知识与典型例题 1.同余的定义 知识点 1.同余的定义...
高中数学奥赛辅导 第三讲 同余
高中数学奥赛辅导 第三讲 同余_学科竞赛_高中教育_教育专区。数学奥赛辅导 第三讲 同余知识、方法、技能同余是数论中的重要概念, 同余理论是研究整数问题的重要工作之...
第三讲 同余理论
第三讲 同余理论_理学_高等教育_教育专区。教学资料第二章 同余理论 2.1 同余...小学奥数竞赛专题之同余... 12页 免费 同余 3页 免费©2014 Baidu 使用百度...
第三讲同余的概念和性质
龙岗学校高中数学联赛提高班讲义 和斌涛 2013 年 12 月 10 日 第3讲一、知识要点 同余的概念和性质 1.设 m 是一个给定的正整数,如果两个整数 a 与 b ...
竞赛专题--同余
竞赛专题--同余_学科竞赛_高中教育_教育专区。第5讲 同余 【知识点】 1.设 m 是一个给定的正整数,如果两个整数 a 与 b 用 m 除所得的余数相同,则称 a...
竞赛讲座 03同余式与不定方程
系列文档 朝鲜历届领导人资料 朝鲜现状 为什么南北朝鲜会分裂 朝鲜的近代史...竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容...
数学奥赛辅导 第三讲 同余
欢迎光临《 欢迎光临《中学数学信息网》 信息网》 zxsx127@163.com 数学奥赛辅导 第三讲 同余知识,方法,技能同余是数论中的重要概念, 同余理论是研究整数问题的...
奥赛专题 -- 同余问题
数学奥赛辅导_第三讲_同_余... 11页 免费 奥赛专题(4) 9页 1财富值喜欢此文档的还喜欢 应用同余问题 4页 免费 小学奥数竞赛专题之同余问... 12页 免费 ...
更多相关标签:
第三讲 同余 一 | 同余定理 | 同余方程 | 线性同余法 | 同余问题 | 线性同余法产生随机数 | 同余式 | 线性同余发生器 |