数学竞赛辅导讲座：同余

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

数学竞赛辅导讲座：同余

知识、方法、技能

同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.

Ⅰ.基本概念

定义一：设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b（modm）；否则，记为ab（modm）.

例如，15≡7（mod4），－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.则,anxn a1x a0 bnxn b1x b0(modm).特别地，设f(x) anxn a1x a0(ai Z),若a b(modm)，则f(a) f(b)(modm).

（5）若ac bc(modm),则a bm).特别地，又若（c,m）=1，则a b(modm). (m,c)

【证明】因m|c(a b),这等价于abmc|(a b).又因若（a,b）=d (,)=1dd(m,c)(m,c)

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

（d≠0）及b|ac，且（b,c）=1 b|a, 从而有m|(a b). (m,c)

这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.

（6）a b(modm),而d|m(d 0),则a b(modd).

（7）设a b(modm),

①若c>0，则ac bc(modmc);

②d为a、b、m的任一公约数，则abm (mod). ddd

（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是数集kr qm r|m是模,r是余数,q Z ,也即kr a|a Z且a r(modm) ,它是一个公差为m的（双边无穷）等差数列.

根据定义，剩余类具有如下性质：

（1）Z k0 k1 k2 km 1,而ki kj (i j);

（2）对任一数n∈Z，有惟一的r0使n kr0；

（3）对任意的a,b∈Z，a,b kr a b(modm).

定义三：设k0,k1, ,km 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等

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

等都是模的4的一个完全剩余系.

显然，模m的完全剩余系有无穷多个.但最常用的是下面两种：

（1）非负数最小完全剩余系：0，1，2， ，m－1；

（2）绝对值最小完全剩余系：它随m的奇偶性不同而略有区别.

当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,a2, ,am是模m的一个完系 当i j时,aiaj(modm) 定理二：设（b,m）=1，c为任意整数.若a1,a2, ,an为一个完系，则ba1 c,ba2 c, ,bam c也是模m的一个完全剩余系.

特别地，任意m个连续整数构成模m的一个完全剩余系.

【证明】只需证明：当i j时,bai c baj 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；等等

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

都是模6的简化剩余类.

由此定义，不难得到：

定理三:a1,a2, ,a (m)是模m的简化剩余系 (ai,m) 1,且aiaj(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为质数，，则ap 1 1(modp).

定理七：（威尔逊定理）设p素数，则（p－1）！ 1(modp).

定理八：（欧拉函数值计算公式）令m的标准分解式为

m p11p22 pkk，

则 (m) m (1

i 1k 1 ).pi

例如，30=2·3·5，则 (30) 30(1 )(1 )(1 ) 8.

读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.

Ⅲ.同余方程

设f(x) anx an 1x

程式的有关定义，我们有

定义六：同余式f(x) 0(modm),an0(modm)叫做一元n次同余方程.例如， nn 1121315 a1x a0为x的整系数多项式.类似于多项式和代数方9x7 3x5 5x2 3 0(mod3)是七次同余方程.

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

定义七：若c使得f(c) 0(modm)成立,则x c(modm)叫做同余方程f(x) 0(modm)的一个解.

显然，同余方程的解是一些剩余类，而不仅是一个或n个类.例如，x 1(mod5), x 4(mod5)都是二次同余方程x2 1(mod5)的解.

1．一次同余方程

ax b(modm)（其中a）称为一次同余方程.关于它的解，有如下共知的结论： 定理九：若（a,m）=1，则ax b(modm)有一个解.

定理十：若（a,m）=d>1，b，则ax b(modm)无解，其中a0(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，

其中 abm, ,m1 . ddd

下面介绍一次同余方程

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 bb(modm)(仅只是形式上的记号），然后用与m互质aa

的数陆续乘右端的分子分母，直至把分母绝对值变成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个同余方程：fk(x) 0(modmk),k 1,2, ,n.则r叫做这n个同余方程组成的同余方程组的解.

定理十二：对同余方程组

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

x c1(modm1),

x c2(modm2).

记(m1,m2) d,[m1,m2] M.

①若1 c2，则此同余方程组无解；

②若d|c1 c2，则此同余方程组有对模M的一类剩余解.

Ⅳ.模m的阶和中国剩余定理

（1）模m的阶

定义九：设m>1是一个固定的整数，a是与m互素的整数，则存在整数k，1 k＜m，使得ak 1(modm).我们将具有这一性质的最小正整数（仍记为k）称为a模m的阶.

a模m的阶具有如下性质：

u, 是任意整数，①设(a,m) 1,k是a模m的阶，则au av(modm)的充要条件是u (modk).

特别地，au 1(modm)的充分必要条件是k|u.

【简证】充分性显然.

必要性.设u ,记l u ,则由a a(modm)及(a,m) 1易知a1(modm).用带余除法，l kq r,这里0 r k,故akqu l ar 1(modm),即ar 1(modm).由0 r k及k的定义知，必须r=0，所以u r(modk).

②设(a,m) 2,a模m的阶为k，则数列a,a,a, ,模m是周期的，且最小正周期是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=

同余方程组 x ci(modmi)(i 1,2, ,n) 2k23 mi,Mi i 1nM(i 1,2, ,n)则mi

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

有且只有解 x M c(modM). （△） iii

i 1n

其中Mi i 1(modmi),i 1,2, ,n. （△△）

【证明】由(mi,mj) 1(i j)知，(Mi,mj) 1，因此每一个同余方程Miy 1(modmi) （i=1，2， n）都有解，于是必存在 i,使得Mi i 1(modm).又因M miMi,mi|Mi(i j), 所以对模mi(i 1,2, ,n)有M1 1c1 Mi ici Mn ncn Mi ici ci(modmi).故（△△）是（△）的解.

若x1,x2是适合（△）的任意两个解，则x1 x2(modmi),i 1,2, ,n,因(mi,mj) 1(i j). 故x1 x2(modm1m2 mn),即x1 x2(modM),因此，（△△）是（△）的惟一解.

赛题精讲

例1：数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里n m 1. （第20届IMO试题）

【解】由已知1978 1078(mod1000),而1000=8×125，所以

1978 1078(mo8d) ① nmnm

1978n 1078m(mod125) ②

因n m 1，且（1978m，125）=1，则由②式知1978nm≡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（mod25）.－

故可令19784=5t+1，而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 2(mod8) ④ nm

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

由于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称为它的周期.

n例如，（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]表示不超过x的最大整数. （第29届IMO预选题）

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

3211, 1, 2222 a,由于f( ) 2 3 ( 3 2 2 1) 2 3 0,于是

,| | .

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

2222 22 6a2 a3 2a3 a3

( ) 2 (3 a) 9 9 1 (8 a2) aaa

a2 (22)2 8, 2 2 1.

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

为了估计[a1788]、[a1988]，先一般考察[an]，为此定义：

un n n an.(n 0,1,2, )

直接计算可知：u0 3,u1 2 a 3.u2 2 2 a2 9,以及un 3 3un 2 n(n 0). 又因0 n n 1( | | ,即 n n 0,又 3 2 22 1,当n 2时， n n | |n n 2 2 1),则an un ( n n) un 1 [1 ( n n)].

[an] un 1.(n 1,2, )

由此知，命题变为证明：u1788 1和u1988 1能被17整除.

现考察 un 在模17的意义下的情况：

u0 3,u1 3,u2 9,u3 7,u4 1,u5 11,u6 9,u7 9,u8 16,u9 5,u10 6,u11 2, u12 1,u13 14,u14 6,u15 0,u16 3,u17 3,u18 9,

可见，在模17意义下， un 是16为周期的模周期数列，即un 16 un(mod17).由于 1788 12(mod16),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 a2n2 a8n8. （第26届IMO预选题）

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

n 1G 1 3 3 3 显然 max， 2n

mixG 1 3 32 3n H.

且G中的元素个数有3n 1 2H 1个.又因G中任意两数之差的绝对值不超过2H，所以G

中的数对模2H+1不同余.因此，G的元素恰好是模2H+1的一个绝对值最小的完系，于是，

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

凡满足 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}.下只需证rj 1与rj(1 j n 2).因为，若如此，当r1的颜色确定后，M中所有都与r1同色.

由于(j 1)k rj 1(modn),则rj k rj 1(modn)，因此，

（1）若rj k n,则rj 1 rj k，于是，由条件（i）知，k rj 1 n rj与n (n rj) rj同色.又由条件（ii）知，k rj 1与|k rj 1 k| rj 1同色，故rj 1与rj同色.

综上所述可知，rj 1与rj同色.命题得证.

例5：设a和m都是正整数，a>1.证明：m| (a 1).

【证明】实上，显然a与a 1互素，且a模a 1的阶是m，所以由模阶的性质③导出m| (a 1).

例6：设p是奇素数，证明：2p－1的任一素因了具有形式2px 1,x是正整数.

【证明】设q是2p－1的任一素因子，则q≠2.设2模q的阶是k，则由2 1(modq)知k|p，故k=1或p（因p是素数，这是能确定阶k的主要因素）.显然k≠1，否则2 1(modq),这不可能，因此k=p.

现在由费马小定理2q 11pmmmm 1(modq)推出k|q 1,即p|q 1.因p、q都是奇数，故q－1=2px（x是个正整数），证毕.

例7：设m,a,b都是正整数，m>1，则m 1,m 1) m

ab(a,b) 1.

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

【证明】记d (ma 1,mb 1).由于（a,b）|a及（a,b）|b，易知m(a,b) 1|ma 1及 m(a,b) 1|mb 1，故m(a,b) 1|d，

另一方面设m模d的阶是k，则由

ma 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，使 y，且x y k.

如p=2，则条件表明k为偶数，可取x 1,y k 1;如p 2,则x 1,y k 1或x 1,y k 2中有一对满足要求.

一般情形下，设n p11 prr是n的标准分解，上面已证明，对每个pi，均有整数xi，

yi，使pixiyi，且xi yi k(1,2, ,r).现在孙子定理表明，同余方程组

1x x1(modp1), ,x xr(modprar)有解x，同样

1y y1(modp1), ,y yr(modprar)

也有解y.现在易证x,y符合问题中的要求：因pi iyi，故pixy（i=1， ，r），于是（xy，n）=1.又x y xi yi k(modpi1)(i 1, ,r),故x y k(modn).

例9：设n为任意的正整数.证明：一定存在n个连续的正整数解，使其中任何一个都不是质数的整数幂. （第30届IMO试题）

【证明】取2n个两两不同的质数p1,p2, ,pn和q1,q2, ,qn.同余方程组x i(modpiqi), i 1,2, ,n.由于p1q1,p2q2, ,pnqn两两互质，根据孙子定理必有解，取为正整数N，则n个连续正整数N+1，N+2， ，N+n都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕.

2010年中学数学竞赛辅导讲座(经典竞赛辅导资料)

.

本文来源：https://www.bwwdw.com/article/dhhj.html