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

高中数学奥赛辅导 第三讲 同余


数学奥赛辅导 第三讲 同余
知识、方法、技能
同余是数论中的重要概念, 同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概 念,剩余类和完全剩余系,同余方程,整数模的阶和中国剩余定理. Ⅰ.基本概念 定义一:设 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(modm) ? m | a. (2) a ? a(modm)(反身性)

a ? b(modm) ? b ? a (modm)(对称性) a ? b(modm)? ? ? a ? c(modm)(传递性) b ? c(modm) ?
(3)若 a ? b(modm), c ? d (modm),则 ① a ? c ? b ? d (modm); ② ac ? bd(modm). (4)若 ai ? bi (modm),i ? 0,1,2,?, n.则, an x n ? ? ? a1 x ? a0 ? bn x n ? ? ? b1 x ? b0 (modm). 特别 地,设 f ( x) ? an x n ? ? ? a1 x ? a0 (ai ? Z ),若a ? b(modm) ,则 f (a) ? f (b)(modm). (5)若 ac ? bc(modm),则a ? b(mod

m ).特别地,又若(c,m)=1,则 a ? b(modm). (m, c)

【证明】因 m | c(a ? b), 这等价于 ≠0)及 b|ac,且(b,c)=1 ? b | a,

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

从而有

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

这个性质说明同余式两边的同一非零因数,不能像等式那样“约去” ,只有当这非零因数与

模互质时,才可“约去”. (6) a ? b(modm), 而 d | m(d ? 0),则a ? b(modd ). (7)设 a ? b(modm), ①若 c>0,则 ac ? bc(modm c); ②d 为 a、b、m 的任一公约数,则

a b m ? (mod ). d d d

(8)若 a ? b(modm1 ), a ? b(modm2 )且(m1 , m2 ) ? 1, 则a ? b(modm1m2 ). (9)若 a ? b(modm),则(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 (modm)? ,它是 一个公差为 m 的(双边无穷)等差数列. 根据定义,剩余类具有如下性质: (1) Z ? k0 ? k1 ? k 2 ?? k m?1 , 而ki ? k j ? ? (i ? j); (2)对任一数 n∈Z,有惟一的 r0 使n ? k r0 ; (3)对任意的 a,b∈Z,a,b ? k r ? a ? b(modm). 定义三:设 k 0 , k1 ,?, k m?1 是模 m 的(全部)剩余类.从每个 kr 中任取一个数 ar,这 m 个数

a0 , a1 ,?, am?1 组成的一个组称为模 m 的一个完全剩余系,简称完系.
例如,取 m=4,则有 k0 ? ? ?,?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 的奇偶性不同而略有区别.

时, 为 ? k ,?(k ? 1),?,?1,0,1,?, (k ? 1), k. (对称式) 当 m ? 2k ? 1
当 m ? 2k时, 为 ? (k ? 1),?(k ? 2),?,?1,0,1, (k ? 1), k.或 ? k ,?(k ? 1),?,?1,0,1,?, (k ? 1). 由定义不难得到如下判别完全剩余系的方法:

定理一:m 个整数 a1 , a2 ,?, am 是模 m 的一个完系 ? 当i ? j时, ai ≡ a j (modm) 定理二:设(b,m)=1,c 为任意整数.若 a1 , a2 ,?, an 为一个完系,则 ba1 ? c, ba2 ? c,?, bam ? c 也 是模 m 的一个完全剩余系. 特别地,任意 m 个连续整数构成模 m 的一个完全剩余系. 【证明】只需证明:当 i ? j时, bai ? c ? ba j ? c(modm). 而这可用反证法得证.下略. 设 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(modm). 于是由性质 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,??,

k5 ? ? ?,?7,?1,5,11,17,??是与模 6 互质的剩余类.数组 1,5;7,-7;1,-1;等等都是
模 6 的简化剩余类. 由此定义,不难得到: 定理三: a1 , a2 ,?, a? (m) 是模 m 的简化剩余系 ? (ai , m) ? 1, 且ai ? a j (modm)(i ? j, i, j ? 1,2,?? (m)). 定理四:在模 m 的一个完全剩余系中,取出所有与 m 互质的数组成的数组,就是一个模 m 的简化剩余系. 这两个定理,前者是简化剩余系的判别方法,后者是它的构造方法.显然,模 m 的简化剩余 系有无穷多个,但常用的是“最小简化剩余系” ,即由 1,2,?,m-1 中与 m 互质的那些数组 成的数组.由定理不难证得简化剩余系的如下性质定理. 定理五:设 a1 , a2 ,?, a? (m) 是模 m 的简化剩余系.若(k,m)=1,则 ka1 , ka2 ,?, ka? ( m) 也是模 m 的简化剩余系.

下面介绍两个有关欧拉函数的重要结论.其证明略. 定理六: (欧拉定理)若(a,m)=1,则 a? ( m) ? 1(modm) 特别地, (费马小定理)若 m=p 为质数,p a,则 a p?1 ? 1(mod p). 定理七: (威尔逊定理)设 p 素数,则(p-1) ! ? ?1(mod p). 定理八: (欧拉函数值计算公式)令 m 的标准分解式为
?k ?1 ?2 , m ? p1 p2 ? pk
k



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

1 ). pi

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

1 2

1 3

1 5

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

x ? 4(mod5) 都是二次同余方程 x 2 ? 1(mod5) 的解.
1.一次同余方程

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

? (modm1 ) 的

一个解为 x ? r (modm1 ), 则 d 个解为: x ? r ? km1 (modm), k ? 0,1,?, d ? 1 , 其中 ? ?

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

下面介绍一次同余方程

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

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

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

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

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

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

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

? x ? c1 (modm1 ), ? ? x ? c 2 (modm2 ).
记 (m1 , m2 ) ? d , [m1 , m2 ] ? M . ①若 d c1 ? c2 ,则此同余方程组无解; ②若 d | c1 ? c2 ,则此同余方程组有对模 M 的一类剩余解. Ⅳ.模 m 的阶和中国剩余定理 (1)模 m 的阶 定义九:设 m>1 是一个固定的整数,a 是与 m 互素的整数,则存在整数 k,1?k<m,使得

a k ? 1(modm) .我们将具有这一性质的最小正整数(仍记为 k)称为 a 模 m 的阶.
a 模 m 的阶具有如下性质: ①设 (a, m) ? 1, k是a模m 的阶, u ,? 是任意整数,则 a u ? a v (modm) 的充要条件是 u ? ? (modk ) . 特别地, a ? 1(modm) 的充分必要条件是 k|u.
u

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

?

法, l ? kq ? r, 这里0 ? r ? k , 故a kq ? a r ? 1(modm),即a r ? 1(modm). 由0 ? r ? k 及 k 的定义 知,必须 r=0,所以 u ? r (modk ). ②设 (a, m) ? 2, a 模 m 的阶为 k,则数列 a, a 2 , a 3 ,?, 模 m 是周期的,且最小正周期是 k, 而 k 个数 a, a 2 , ?, a k 模 m 互不同余. ③设 (a, m) ? 1, 则a 模 m 的阶整除欧拉函数 ? (m). 特别地,若 m 是素数 p,则 a 模 p 的阶整 除 p-1. (2)中国剩余定理(即孙子定理) 设 n ? 2, m1 , m2 ,?, mn 是两两互质的正整数,记 M= 方程组

?m , M
i i ?1

n

i

?

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

x ? ci (modmi )(i ? 1,2,?, n)
x ? ? M i? i ci (modM ).
i ?1 n

有且只有解

(△)

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

(△△)

【证明】由 (mi , m j ) ? 1(i ? j) 知, (M i , m j ) ? 1 ,因此每一个同余方程 M iy ? 1(modmi ) (i=1,2,?n)都有解,于是必存在 ? i , 使得M i? i ? 1(modm).又因M ? mi M i , mi | M i (i ? j), 所以对模 mi (i ? 1,2,?, n)有M1?1c1 ? ? ? M i? i ci ? ? ? M n? n cn ? M i? i ci ? ci (modmi ). 故 (△△)是(△)的解. 若 x1 , x 2 是适合(△)的任意两个解,则 x1 ? x2 (modmi ), i ? 1,2, ?, n,因(mi , m j ) ? 1(i ? j). 故 x1 ? x2 (modm1m2 ?mn ),即x1 ? x2 (modM ), 因此, (△△)是(△)的惟一解.

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

1 9 7n8? 1 0 7m8 ( m o8 d ) 1978n ? 1078m (mod125)

① ②

因 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 的最小值. 先确定 k 的最小值:因为 19784=(79×25+3)4≡34≡1(mod5) ,19784≡34≡1(mod25).


故可令 19784=5t+1,而 5 t,从而 0≡1978n

-m

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

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

125) ,显然,使上式成立的 k 的最小值为 25. + k ? 5t (mod
再确定 m 的最小值:因 1978≡2(mod8) ,则由①式知, 2 n ? 2 m (mod8) 由于 n ? m ? 1, ④式显然对 m=1,2 不成立,从而 m 的最小值为 3. 故合于题设条件的 n+m 的最小值为 106. 【评述】比例中我们用了这样一个结论:1978 的各次方幂的个位数字是以 8,4,2,6 循环
4q?r 出现,即,当 r=1,2,3,4 时,1978p ? 1978 ? 8,4,2,6(mod10). 这种现象在数学上称为“模



同期现象”.一般地,我们有如下定义: 整数列 ?xn ? 各项除以 m(m?2,m∈N*)后的余数 an 组成数列 ?an ? .若 ?an ? 是一个周期数 列,则称 ?xn ? 是关于模 m 的周期数列,简称模 m 周期数列.满足 an?T ? an (或 an?T ? xn (modm) )的最小正整数 T 称为它的周期. 例如, (1) 1978 是模 10 周期数列,周期为 4; (2)自然数列{n}是一个模 m(m?2,m ∈N*)周期数列,周期为 m; (3)任何一个整数等差数列都是一个模 m(m?2,m∈N*)周期 数列,周期为 m. 例 2:设 a 是方程 x ? 3x ? 1 ? 0 的最大正根,求证:17 可以整除[a1788]与[a1988].其中[x]表
3 2

?

n

?

示不超过 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],为此定义:

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

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

u0 ? 3, u1 ? 3, u2 ? 9,u 3 ? 7, u4 ? 1, u5 ? 11, u6 ? 9,u 7 ? 9, u8 ? 16, u9 ? 5, u10 ? 6,u11 ? 2,

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

u1788 ?1 ? 0, u1988 ? 1 ? 0(mod17). 命题得证.
例 3: 求八个整数 n1 , n2 ,?, n8 满足: 对每个整数 k (-1985<k<1985) , 有八个整数 a1, a2, ?, a8∈{-1,0,1},使得 k ? a1n1 ? a2 n2 ? ? ? a8 n8 . (第 26 届 IMO 预选题)

【解】令数集 G ? k | k ? a1 ? a2 ? 3 ? a3 ? 32 ? ? ? an?1 ? 3n , ai ?{?1,0,1}, i ? 1,2,?, n ? 1 .

?

?

显然

3n?1 ? 1 max G ? 1? 3 ? 3 ??? 3 ? 2
2 n



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,且可惟一地表示为: a1 ? a2 ? 3 ? a3 ? 32 ? ? ? an?1 ? 3n 形式.
当 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)k 也是模 n 的一个完全剩余系.若设 jk ? rj (modn)(其中 1 ? rj ? n ? 1, j ? 1,2,?, n ? 1), 则 M= {r1 , r2 ,?, rn?1}. 下只需证 r j ?1与rj (1 ? j ? n ? 2). 因为,若如此,当 r1 的颜色确定后,M 中 所有都与 r1 同色. 由于 ( j ? 1)k ? rj ?1 (modn),则rj ? k ? rj ?1 (modn) ,因此, (1)若 r j ? k ? n, 则r j ?1 ? r j ? k ,于是,由条件(i)知, k ? r j ?1 ? n ? r j 与n ? (n ? r j ) ? r j 同色.又由条件(ii)知, k ? r j ?1与 | k ? r j ?1 ? k |? r j ?1 同色,故 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 m ? 1).
例 6:设 p 是奇素数,证明:2p-1 的任一素因了具有形式 2 px ? 1, x 是正整数. 【证明】 设 q 是 2p-1 的任一素因子, 则 q≠2.设 2 模 q 的阶是 k, 则由 2 ? 1(modq) 知 k|p,
p

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

能,因此 k=p. 现在由费马小定理 2 (x 是个正整数) ,证毕. 例 7:设 m,a,b 都是正整数,m>1,则 m ? 1, m ? 1) ? m
a b a b ( a ,b ) q ?1

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

? 1.
( a ,b )

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

? 1 | ma ? 1 及

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

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

? 1. 证毕.

例 8:设 n,k 是给定的整数,n>0,且 k(n-1)是偶数.证明:存在 x, y, 使得( x, n) ? ( y, n) ? 1, 是 x ? y ? k (modn). 【证明】我们先证明,当 n 为素数幂 p ? 时结论成立.实际上,我们能证明,存在 x,y,使 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 ? pr r 是 n 的标准分解,上面已证明,对每个 pi ,均有整数 x i , yi , 使 pi xiyi,且 xi ? yi ? k (1,2,?, r ).现在孙子定理表明,同余方程组
?1 x ? x1 (mod p1 ),?, x ? xr (mod prar ) 有解 x,同样
? ?

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

也有解 y.现在易证 x,y 符合问题中的要求:因 pi xiyi,故 pi xy(i=1,?,r) ,于是(xy,n)=1. 又 x ? y ? xi ? yi ? k (mod pi 1 )(i ? 1,?, r ),故x ? y ? k (modn). 例 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 都至少含有两个不同的质因数,因而它们中的任一个都不是质 数的整数幂.证毕.


相关文章:
高中数学奥赛辅导 第三讲 同余
高中数学奥赛辅导 第三讲 同余_学科竞赛_高中教育_教育专区。数学奥赛辅导 第三讲 同余知识、方法、技能同余是数论中的重要概念, 同余理论是研究整数问题的重要工作之...
数学奥赛辅导 第三讲 同余
欢迎光临《 欢迎光临《中学数学信息网》 信息网》 zxsx127@163.com 数学奥赛辅导 第三讲 同余知识,方法,技能同余是数论中的重要概念, 同余理论是研究整数问题的...
第三讲 同余
第三讲 同余_学科竞赛_高中教育_教育专区。高中竞赛初等数论选讲,共6讲初等代数选讲---第三讲 第三讲 同余 同余的性质应用非常广泛,在处理某些整除性、进位制、...
2013高中数学奥数培训资料之同余
关键词:奥林匹克奥数数学竞赛高中 1/4 同系列文档 2013高中数学奥数培训资料.....2013高中数学奥数培训资料之同余 2012年最新高中奥数辅导资料专题,数学联赛获奖不是...
高中数学竞赛讲座 03同余式与不定方程
高中数学竞赛讲座 03同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛...
数学奥赛辅导_第三讲_同_余
关键词:高中数学竞赛辅导 同系列文档 数学奥赛辅导_第一讲_奇数... 数学奥赛辅导...数学奥赛辅导同余知识、方法、技能 第三讲 同余是数论中的重要概念, 同余理论是...
高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)
高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)_学科竞赛_高中教育_...高中数学竞赛培训专题讲... 5页 免费 高中数学竞赛专题讲座--... 8页 免费...
高中数学奥林匹克竞赛讲座:03同余式与不定方程
高中数学奥林匹克竞赛讲座:03同余式与不定方程_高一数学_数学_高中教育_教育专区。高中数学奥林匹克竞赛讲座竞赛讲座 03 --同余式与不定方程 同余式与不定方程同余...
人教版高中数学竞赛讲座:同余式与不定方程
人教版高中数学竞赛讲座:同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容.考虑...
高中数学竞赛培训专题4---同余式与不定方程
高中数学竞赛培训专题4---同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛培训专题 7---同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容....
更多相关标签:
第三讲 同余 一 | 高中数学初等数论同余 | 高中数学奥赛辅导总结 | 高中奥赛辅导方案 | 高中物理奥赛辅导 | 高中化学奥赛辅导 | 高中化学奥赛辅导书 | 高中数学奥赛辅导书 |