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

1、12设设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是正整数。是正整数。 3设设a=q1m+r1，0r1m；b=q2m+r2，0r2m。于是于是a-b=(q1-q2)m+(r1-r2)由此式，由此式，m|(a-b)必要而且只要必要

2、而且只要m|(r1-r2)，但但|r1-r2|m，故故m|(r1-r2)必要而且只要必要而且只要r1-r2=0。因之，因之，ab(mod m)必要而且只要以必要而且只要以m除除a和和b所得的余数相同。所得的余数相同。 4567891011)9(modN0niianiia0121314含有整数变量的合同式，称为合同方程含有整数变量的合同式，称为合同方程或同余式或同余式 。ax b(mod m)这种形式的合同式称为一次这种形式的合同式称为一次同余式；类似地，同余式；类似地，a2x2+a1x b(mod m)称为称为二次同余式。二次同余式。 15求解一次同余式实际上是解求解一次同余式实际上是解 ax

3、-b=my这样这样的不定方程。我们这里讨论一次同余式在的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？有多解（多个剩余类）？ 16若若a和和m互质，互质，b任意，则模任意，则模m恰有一个数恰有一个数x使使ax b(mod m) 。证明：证明： 存在性存在性。因为。因为a和和m互质，故有互质，故有s，t使使as+mt=1，于是于是asb+mtb=b，若取模若取模m，则有则有asb b(mod m)。取取x=sb，则则sb所在的剩余类中所在的剩余

4、类中的数皆是解。的数皆是解。唯一性唯一性。所谓模。所谓模m只有一个这样的只有一个这样的x，意思是说意思是说在模在模m合同的意义下，解是唯一的。即若合同的意义下，解是唯一的。即若ax b (mod m)，ay b(mod m)，则则x y(mod m)。因为，因为，由由ax b(mod m)，ay b(mod m)得得ax ay(mod m)，消去和消去和m互质的互质的a乃得乃得x y (mod m)。 17推论推论 设设P为质数。若为质数。若a 0 (mod p)，b任意，任意，则模则模p恰有一个数恰有一个数x使使ax b(mod p)。 18若若(a, m)=d 1，且且d|b，则同余式则同

5、余式ax b (mod m)无解。无解。证明：证明：反证法。若上式可解，则存在反证法。若上式可解，则存在 ，使使得得a b(mod m)。从而存在从而存在q，使得使得b=a -mq。因为因为(a, m)=d 1 ，故故d|(a -mq)，从而从而d|b，矛盾。矛盾。 19若若(a, m)=d 1 ，且且d|b，则同余式则同余式ax b(mod m) (1)有有d个解，分别为个解，分别为 , +m/d, +2m/d, , +(d-1)m/d (2)其中其中 是同余式是同余式(a/d)x b/d (mod m/d) (3)的解。的解。 20证明：证明：由由性质性质11和和性质性质9知知, (1)的

6、解是的解是(3)的的解，解， (3)的解也是的解也是(1)的解。因为的解。因为(a, m)=d，所以所以(a/d, m/d)=1。由由定理定理5.3.1知，知， (3)在模在模m/d下有唯一解，设为下有唯一解，设为 ，不妨设不妨设0 m/d。因为因为 +km/d恰是恰是 所在的模所在的模m/d剩余类的剩余类的全部元素，全部元素，k=0, 1, 2, ，故故(3)的解作为的解作为数都可以表示成数都可以表示成 +km/d的形式。于是的形式。于是(1)的的解都是解都是 +km/d形式的数，形式的数，k=0, 1, 2, 。 21下面证明下面证明(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，0 i d-1，使得使得 l i