合同一次同余式离散数学

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)必要而且只要必要而且只要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-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所在的剩余类中所在的剩余类中的数皆是解。的数皆是解。唯一性唯一性。所谓模。所谓模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，则同余式则同余式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)的解是的解是(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(mod d)。由由m/d 0和性质和性质9，两边和模同乘，两边和模同乘m/d 得，得，(l/d)m (i/d)m(mod m)，故故+lm/d +im/d(mod m)。证毕。证毕。个人观点供参考，欢迎讨论