第六讲 同余

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《第六讲 同余》，欢迎阅读！



第六讲 同余



知识、方法、技能

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

Ⅰ.基本概念 定义一：设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.则,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(m,c)(m,c)dd

- 1 -




（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等



- 2 -


等都是模的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时,ai≡aj(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互质.这样，又可给出如下定义.

- 3 -

本文来源：https://www.wddqxz.cn/08cc29fd1a5f312b3169a45177232f60ddcce7ad.html