《合同 一次同余式》由会员分享，可在线阅读，更多相关《合同 一次同余式（22页珍藏版）》请在金锄头文库上搜索。
1、5.3 合同 一次同余式 5.3.1 合同及其性质 设m是任意非0整数。a被m整除时，我们就 说a 合同于0模m，记为： a0(mod m) 一般来说，若a-b被m整除，则我们说a合同 于b 模m： ab(mod m) 一个数为m整除，当且仅当此数为- m整除 。所以，若未指定m而一般地讨论模m合同 时，我们总假定m是正整数。 5.3.1 合同及其性质 设a=q1m+r1，0r1m；b=q2m+r2， 0r2m。于是 a-b=(q1-q2)m+(r1-r2) 由此式，m|(a-b)必要而且只要m|(r1-r2)，但 |r1-r2|m，故m|(r1-r2)必要而且只要r1-r2=0 。因之，ab
2、(mod m)必要而且只要以m除a 和b所得的余数相同。 合同的基本性质 性质性质1 1 aaaa。 性质性质2 2 若若ab,ab,则则baba。 性质性质3 3 若若abab，bcbc，则则acac。这就是说，合同是一种等价关系。每一个这就是说，合同是一种等价关系。每一个 等价类称为模等价类称为模mm的一个的一个剩余类剩余类。 合同的基本性质 性质性质4 4 若若ab(mod m)ab(mod m)，cd(mod m)cd(mod m)，则则 a a cbcb d(mod d(mod m)m)，acbd(modacbd(mod m) m) 证明：证明：由题设有由题设有r r，s s使使a-
3、b=a-b=rmrm，c-dc-d= =smsm。 故故( (a a c)-(bc)-(b d)=(rd)=(r s)m, s)m, 因而因而a a c c b b d(mod d(mod m)m)。其次，其次， ac=(ac=(b+rm)(d+smb+rm)(d+sm)=bd+rdm+bsm+rsm)=bd+rdm+bsm+rsm2 2 bd+0+0+0(mod m)=bd+0+0+0(mod m)=bd(modbd(mod m) m)，故故 acac bd(modbd(mod m) m)。合同的基本性质 性质性质5 5 若若a a b(mod m)b(mod m)，则则a a k k b
4、b k (mod k (mod m)m)。其中其中k k为整数。为整数。 性质性质6 6 若若a+ba+b c(mod m)c(mod m)，则则a a c-b(mod m)c-b(mod m) 。 性质性质7 7 若若a a b(mod m)b(mod m)，则则acac bc(modbc(mod m) m)。 性质性质8 8 若若a a b(mod m)b(mod m)，则则a an n b bn n(mod(mod m) m)， n n 0 0。 合同的基本性质 性质性质9 9 若若c c 0 0而而acac bc(modbc(mod mc) mc)，则则 a a b(mod m)b(m
5、od m)。 证明：由题设有证明：由题设有q q使使ac-ac-bcbc= =qmcqmc，于是于是a-a- b=b=qmqm，因而因而a a b(mod m)b(mod m)。 性质性质1010 若若c c和和mm互质，则由互质，则由acac bc(modbc(mod m) m) 可以推出可以推出a a b(mod m)b(mod m)。 证明：证明：ac=ac=bc(modbc(mod m) m)表示表示m|(a-b)cm|(a-b)c，但但c c和和 mm互质，所以有互质，所以有m|(a-b)m|(a-b)，于是于是a a b(mod m)b(mod m) 。 合同的基本性质 性质性质1
6、111 若若acac bc(modbc(mod m) m)，且（且（c, mc, m）=d=d， 则则a a b(mod m/d)b(mod m/d) 证明：由证明：由acac bc(modbc(mod m) m)知，知，m|(a-b)cm|(a-b)c，而而( (c, c, m)=dm)=d，故故 m/d | (a-b)c/dm/d | (a-b)c/d。注意到（注意到（m/d, c/dm/d, c/d ）=1=1，从而得从而得 m/d|(a-b)m/d|(a-b)，即即 a a b(mod m/d)b(mod m/d) 。 对于质数模对于质数模p p，则有和相等完全类似的消去则有和相等完全
7、类似的消去 律。律。 合同的基本性质 性质性质1212 若若p p为质数，为质数，c c 0(mod p)0(mod p)，而而 acac bc(modbc(mod p) p)，则则a a b(mod p)b(mod p)。 证明：因为证明：因为p p是质数，是质数，c c 0(mod p) 0(mod p)就表示就表示c c 和和p p互质，互质，( (c, p)=1c, p)=1，因而性质因而性质1212不不 过是性质过是性质1010的推论。的推论。合同的基本性质 性质性质13 13 设设p(x)p(x)是整系数多项式，是整系数多项式，x x和和y y是整是整 数变量，则由数变量，则由x
8、x y(mod m)y(mod m)可得可得 p(x) p(x) p(y) p(y) (mod m)(mod m)。 运用性质运用性质1313，我们看能被，我们看能被9 9整除数的数码特整除数的数码特征。设征。设N=aN=an n1010n n+a+an-1n-11010n-1n-1+a+a1 110+a10+a0 0为一为一整数，因为整数，因为1010 1(1(mod 9)mod 9)，由性质由性质1313得得N N a an n1 1n n+a+an-1n-11 1n-1n-1+a+a1 1+a+a0 0(mod 9)(mod 9)即即 。 于是于是 9| 9|N N当且仅当当且仅当9|
9、9| 5.3.2 剩余类 一次同余式 模模mm合同既然是一种等价关系，就可以把合同既然是一种等价关系，就可以把 所有整数按照模所有整数按照模 mm合同的关系分为等价类合同的关系分为等价类 ，每一个等价类称为模，每一个等价类称为模mm的一个剩余类。的一个剩余类。同一个剩余类中的数互相合同，不同的剩同一个剩余类中的数互相合同，不同的剩 余类中的数不互相合同。余类中的数不互相合同。 因为以因为以mm去除任意整数，可能得到的余数去除任意整数，可能得到的余数 恰有恰有0 0，1 1，m-1m-1，这这mm个数，所以模个数，所以模mm 共有共有mm个剩余类，个剩余类， 5.3.2 剩余类 一次同余式 从每
10、个剩余类中取出一个数作为代表，这从每个剩余类中取出一个数作为代表，这 样便可得到样便可得到mm个数，比方个数，比方r r1 1, r, r2 2, , ,r rmm说是作说是作 成一个完全剩余系，任意整数模成一个完全剩余系，任意整数模mm恰好合恰好合 同于此完全剩余系中的一个数。例如，同于此完全剩余系中的一个数。例如，0 0， 1 1，m-1m-1便是这样一个完全剩余系。又便是这样一个完全剩余系。又 如，模如，模3 3，三个数，三个数0 0，1 1，2 2作成一个完全剩作成一个完全剩 余系，余系，-1-1，0 0，1 1也作成一个完全剩余系。也作成一个完全剩余系。 模模2 2，两个数，两个数0
11、 0，1 1作成一个完全剩余系，作成一个完全剩余系，0 0 代表所有偶数，代表所有偶数，1 1代表所有奇数。代表所有奇数。 同余式 含有整数变量的合同式，称为合同方程或 同余式 。 axb(mod m)这种形式的合同式称为一次 同余式；类似地，a2x2+a1xb(mod m)称为 二次同余式。 同余式求解一次同余式实际上是解 ax-b=my这样 的不定方程。我们这里讨论一次同余式在 什么条件下有解？什么条件下无解？什么 时候有唯一解（一个剩余类）？什么时候 有多解（多个剩余类）？ 定理5.3.1 若a和m互质，b任意，则模m恰有一个数x使 axb(mod m) 。 证明： 存在性。因为a和m互
12、质，故有s，t使 as+mt=1，于是asb+mtb=b，若取模m，则有 asbb(mod m)。取x=sb，则sb所在的剩余类中 的数皆是解。 唯一性。所谓模m只有一个这样的x，意思是说 在模m合同的意义下，解是唯一的。即若axb (mod m)，ayb(mod m)，则xy(mod m)。因为 ，由axb(mod m)，ayb(mod m)得axay(mod m)，消去和m互质的a乃得xy (mod m)。 定理5.3.1推论 设P为质数。若a 0 (mod p)，b任意，则模p恰有一个数x使axb(mod p)。 定理5.3.2若(a, m)=d1，且d|b，则同余式axb (mod m
13、)无解。证明：反证法。若上式可解，则存在，使 得ab(mod m)。从而存在q，使得b=a- mq。因为(a, m)=d1 ，故d|(a-mq)，从而 d|b，矛盾。 定理5.3.3若(a, m)=d1 ，且d|b，则同余式 axb(mod m) (1) 有d个解，分别为, +m/d, +2m/d, , +(d-1)m/d (2) 其中是同余式 (a/d)xb/d (mod m/d) (3) 的解。 定理5.3.3证明：由性质11和性质9知, (1)的解是(3)的 解， (3)的解也是(1)的解。因为(a, m)=d， 所以(a/d, m/d)=1。由定理5.3.1知， (3)在模 m/d下有
14、唯一解，设为 ，不妨设0 m/d 。 因为+km/d恰是所在的模m/d剩余类的 全部元素，k=0, 1, 2, ，故(3)的解作为 数都可以表示成+km/d的形式。于是(1)的 解都是+km/d形式的数，k=0, 1, 2, 。 定理5.3.3下面证明(2)式是(1)的d个不同解。因为0 m/d ，故0 (2)中每一个式子 m，且互不相同，所以 它们之间关于模m互不同余，即(2)为(1)的d个不 同解。 再考虑(1)只有(2)这d个不同解。即若数+lm/d是 (1)的解，则关于模m， +lm/d必同余(2)中d个数 之一。 因为 0，1，d-1为关于模d的完全剩余系， 故存在i，0id-1，使得 li (mod d)。由m/d0 和性质9，两边和模同乘m/d 得，(l/d)m (i/d)m (mod m)，故+lm/d +im/d(mod m)。证毕。 作业：170页 2
