合同一次同余式(离散数学).ppt

《合同一次同余式(离散数学).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§5.3合同一次同余式§5.3.1合同及其性质设m是任意非0整数。a被m整除时，我们就说a合同于0模m，记为：a0(modm)一般来说，若a-b被m整除，则我们说a合同于b模m：ab(modm)一个数为m整除，当且仅当此数为-m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。§5.3.1合同及其性质设a=q1m+r1，0≤r1

2、(a-b)必要而且只要m

3、(r1-r2)，但

4、r1-r2

5、

6、(r1-r2)必要而且只要r1-r2=0。因之，a≡b(modm)必要而且只要以

7、m除a和b所得的余数相同。合同的基本性质性质1a≡a。性质2若a≡b,则b≡a。性质3若a≡b，b≡c，则a≡c。这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。合同的基本性质性质4若a≡b(modm)，c≡d(modm)，则ac≡bd(modm)，ac≡bd(modm)证明：由题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m,因而acbd(modm)。其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(modm)=bd(modm)，故acbd(modm)。合同的基本性质性质5若ab(modm)

8、，则akbk(modm)。其中k为整数。性质6若a+bc(modm)，则ac-b(modm)。性质7若ab(modm)，则acbc(modm)。性质8若ab(modm)，则anbn(modm)，n0。合同的基本性质性质9若c0而acbc(modmc)，则ab(modm)。证明：由题设有q使ac-bc=qmc，于是a-b=qm，因而ab(modm)。性质10若c和m互质，则由acbc(modm)可以推出ab(modm)。证明：ac=bc(modm)表示m

9、(a-b)c，但c和m互质，所以有m

10、(a-b)，于是ab(modm)。合同的基本性质性质11若acbc

11、(modm)，且（c,m）=d，则ab(modm/d)证明：由acbc(modm)知，m

12、(a-b)c，而(c,m)=d，故m/d

13、(a-b)c/d。注意到（m/d,c/d）=1，从而得m/d

14、(a-b)，即ab(modm/d)。对于质数模p，则有和相等完全类似的消去律。合同的基本性质性质12若p为质数，c0(modp)，而acbc(modp)，则ab(modp)。证明：因为p是质数，c0(modp)就表示c和p互质，(c,p)=1，因而性质12不过是性质10的推论。合同的基本性质性质13设p(x)是整系数多项式，x和y是整数变量，则由xy(modm)可得p(x)p(y)(

15、modm)。运用性质13，我们再看能被9整除数的数码特征。设N=an10n+an-110n-1+…+a110+a0为一整数，因为101(mod9)，由性质13得Nan1n+an-11n-1+…+a1+a0(mod9)即。于是9

16、N当且仅当9

17、§5.3.2剩余类一次同余式模m合同既然是一种等价关系，就可以把所有整数按照模m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。因为以m去除任意整数，可能得到的余数恰有0，1，…，m-1，这m个数，所以模m共有m个剩余类，§5.3.2剩余类一次同余式从每个剩余类中取出一个数作为代表，这

18、样便可得到m个数，比方r1,r2,…,rm说是作成一个完全剩余系，任意整数模m恰好合同于此完全剩余系中的一个数。例如，0，1，…，m-1便是这样一个完全剩余系。又如，模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数。同余式含有整数变量的合同式，称为合同方程或同余式。axb(modm)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(modm)称为二次同余式。同余式求解一次同余式实际上是解ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯

19、一解（一个剩余类）？什么时候有多解（多个剩余类）？定理5.3.1若a和m互质，b任意，则模m恰有一个数x使axb(modm)。证明：存在性。因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(modm)。取x=sb，则sb所在的剩余类中的数皆是解。唯一性。所谓模m只有一个这样的x，意思是说在模m合同的意义下，解是唯一的。即若axb(modm)，ayb(modm)