5-3合同 一次同余式.ppt

文档介绍：§ 合同 一次同余式
1
编辑ppt
§ 合同及其性质
设m是任意非0整数。a被m整除时，我们就说a 合同于0模m，记为： a0(mod m)
一般来说，若a-b被m整除，则我们说a合同于b 模m： ab(mod m)
一个数为m整除，当且仅当此数为- m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。
2
编辑ppt
§ 合同及其性质
设a=q1m+r1，0≤r1<m；b=q2m+r2，0≤r2<m。于是 a-b=(q1-q2)m+(r1-r2)
由此式，m|(a-b)必要而且只要m|(r1-r2)，但|r1-r2|<m，故m|(r1-r2)必要而且只要r1-r2=0。因之，a≡b(mod m)必要而且只要以m除a和b所得的余数相同。
3
编辑ppt
合同的基本性质
性质1 a≡a。
性质2 若a≡b,则b≡a。
性质3 若a≡b，b≡c，则a≡c。
这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。
4
编辑ppt
合同的基本性质
性质4 若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)，ac≡bd(mod m)
证明：由题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m, 因而acbd(mod m)。其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(mod m)=bd(mod m)，故acbd(mod m)。
5
编辑ppt
合同的基本性质
性质5 若ab(mod m)，则akbk (mod m)。其中k为整数。
性质6 若a+bc(mod m)，则ac-b(mod m)。
性质7 若ab(mod m)，则acbc(mod m)。
性质8 若ab(mod m)，则anbn(mod m)， n0。
6
编辑ppt
合同的基本性质
性质9 若c0而acbc(mod mc)，则ab(mod m)。
证明：由题设有q使ac-bc=qmc，于是a-b=qm，因而ab(mod m)。
性质10 若c和m互质，则由acbc(mod m)可以推出ab(mod m)。
证明：ac=bc(mod m)表示m|(a-b)c，但c和m互质，所以有m|(a-b)，于是ab(mod m)。
7
编辑ppt
合同的基本性质
性质11 若acbc(mod m)，且（c, m）=d，则ab(mod m/d)
证明：由acbc(mod m)知，m|(a-b)c，而(c, m)=d，故 m/d | (a-b)c/d。注意到（m/d, c/d）=1，从而得 m/d|(a-b)，即 ab(mod m/d)。
对于质数模p，则有和相等完全类似的消去律。
8
编辑ppt
合同的基本性质
性质12 若p为质数，c0(mod p)，而acbc(mod p)，则ab(mod p)。
证明：因为p是质数，c 0(mod p)就表示c和p互质，(c, p)=1，因而性质12不过是性质10的推论。
9
编辑ppt
合同的基本性质
性质13 设p(x)是整系数多项式，x和y是整数变量，则由xy(mod m)可得 p(x) p(y) (mod m)。
10
编辑ppt