离散数学课件 8.3同余

同余的概念同余类一次同余式8.3同余第8章数论

同余的概念定义8.7设m是正整数，a与b是整数，若m|(a-b)，则称a模m同余于b，或a与b模m同余（Congruence），记作a≡b(modm)。否则，说a与b模m不同余，记作a≢b(modm)。例如，17=9(mod8)，15=0(mod5)，29≢16(mod9)

同余的概念定义8.8设m是正整数，a与b是整数，若m除a、b的余数相同，则称a与b模m同余。易知a≡b(modm)⇔a=b+mt，t∈Z从定义可以看出，同余与整除间的关系，即整除与同余可以相互转化，因此关于同余的有关问题，我们可以用整除的语言来叙述。

同余的概念定理8.14设a=r₁+mq₁，0≤r₁<mb=r₂+mq₂，0≤r₂<m则a≡b(modm)当且仅当r₁=r₂。

同余的概念证明由已知a-b=(r₁-r₂)+m(q₁-q₂)必要性：设a≡b(modm)，则有m|(a-b)，但是由已知有|r₁-r₂|<m，所以|r₁-r₂|=0，即r₁=r₂。充分性：如果r₁=r₂，则a-b=m(q₁-q₂)，即m|(a-b)，所以a≡b(modm)。即a与b模m同余，当且仅当m除a、b所得的余数相同。作为两个整数之间的一种二元关系，同余具有很多性质。

同余的概念性质8.1同余关系是等价关系自反性：对任意整数a，有a≡a(modm)对称性：若a≡b(modm)，则b≡a(modm)传递性：若a≡b(modm)，b≡c(modm)，则a≡c(modm)同余模的算术运算具有以下性质：如果a≡b(modm)，c≡d(modm)，则(a±c)≡(b±d)(modm)，ac≡bd(modm)

同余的概念性质8.2（1）如果a+b≡c(modm)，则a-c≡b(modm)（2）如果an≡bn(modm)，且gcd(m,n)=1，则a≡b(modm)（3）如果a≡b(modm)，是a,b,m的正公因子，则

同余的概念证明由已知，令a=a₁n,b=b₁n,m=m₁n，因a≡b(modm)，则有a₁n=b₁n+m₁nt,t∈Z从而有a₁=b₁+m₁t,t∈Z（4）如果a≡b(modm)，则gcd(a,m)=gcd(b,m)

同余类定义8.9设m是给定的正整数，则全体正整数可以分为m个类（子集），记为：j₀,j₁,⋯,j{m-1}，其中，ji={mq+i,q∈Z},i=0,1,⋯,m-1。则称j₀,j₁,⋯,j{m-1}为模m的同余类。定理8.15设m是给定的正整数，j₀,j₁,⋯,j{m-1}是模m的同余类，则有（1）每个整数恰包含在一个ji里，0≤i≤m-1。（2）两个整数a,b属于同一类的充要条件是a≡b(modm)。

证明（1）设a是任意整数，则由带余除法得a=r+mt，0≤r≤m−1。所以a在jr

中。

又因为r是由a唯一确定的，所以a只能在jr

中。（2）必要性：设a,b是两个整数，并且都在jr

内，则

a=r+mq₁，b=r+mq₂所以a≡b(modm)充分性：由同余定义可知a,b在某一个同余类jr

内，0≤r≤m−1。同余类

同余类由性质8.1知，同余关系是等价关系，整数a在模m同余关系下的等价类记作[a]m，称做等价类，可简记为am。把整数集合Z在模m同余关系下的商集记作Zm。可以在Zm上定义加法和乘法：对任意的整数a,b，有[a]+[b]=[a+b]，[a]·[b]=[ab]

同余类加法和乘法表见表8.1和表8.2。表8.2乘法表*5[0][1][2][3][4][0][0][0][0][0][0][1][0][1][2][3][4][2][0][2][4][1][3][3][0][3][1][4][2][4][0][4][3][2][1]表8.1加法表+5[0][1][2][3][4][0][0][1][2][3][4][1][1][2][3][4][0][2][2][3][4][0][1][3][3][4][0][1][2][4][4][0][1][2][3]

一次同余式定义8.10设m>0，方程ax≡b(modm)（7.3）称为一次同余式，使上式成立的整数称为同余式的解。由同余性质，如果整数r是其解，则与r同余的所有整数都是其解。

一次同余式定理8.16设a,m∈Z，如果gcd(a,m)=1，则方程（7.3）在同余意义下恰有一个解。证明：由gcd(a,m)=1可知，存在s,t∈Z，使得as+mt=1，于是有asb+mtb=b，从而asb≡b(modm)令x=sb，则有ax≡b(modm)。设∃y∈Z，使得ay≡b(modm)，则由同余性质知ax≡ay(modm)，又gcd(a,m)=1，所以有x≡y(modm)形如

一次同余式定理8.17（孙子定理）如果m₁,m₂,⋯,mₖ两两互素，则同余方程对于模m=m₁m₂⋯mₖ有唯一解。

一次同余式例8.11

（孙子算经）今有物知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？解

由题意得同余方程

一次同余式例8.12

解同余方程组解由2x≡1(mod5)解得x≡3(mod5)，由3x≡4(mod7)解得x≡6(mod7)，于是原同余方程组化为可