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

数学奥赛辅导 第三讲 同余

知识、方法、技能

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

Ⅰ.基本概念

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

例如，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 b(mod

m

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

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

abmc

|(a b).又因若（a,b）=d (,)=1（d

dd(m,c)(m,c)

≠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等等都是模的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时,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；等等都是

模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 1).

pii 1

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

读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选

取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.

Ⅲ.同余方程

设f(x) anxn an 1xn 1 a1x a0为x的整系数多项式.类似于多项式和代数方程式的有关定义，我们有

定义六：同余式f(x) 0(modm),an0(modm)叫做一元n次同余方程.例如，

k

121315

9x7 3x5 5x2 3 0(mod3)是七次同余方程.

定义七：若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个同余方程组成的同余方程组的解.

定理十二：对同余方程组

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的阶具有如下性质：

①设(a,m) 1,k是a模m的阶，u, 是任意整数，则au av(modm)的充要条件是u (modk). 特别地，a 1(modm)的充分必要条件是k|u. 【简证】充分性显然.

必要性.设u ,记l u ,则由a a(modm)及(a,m) 1易知a1(modm).用带余除

u

u

l