第 3 章 同余方程（一） 内容：● 同余方程概念● 解同余方程● 解同余方程组（二） 重点● 解同余方程（三） 应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--Λ其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ） （1） 叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。

（2） 同余方程的解若整数a 使得 f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。

（3） 同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。

即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。

故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。

显然()m f T ;≤m（4） 同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。

【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。

50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。

（解）取模15的绝对最小完全剩余系：－7，－6，…，－1，0，1，2，…，7，直接计算知x ＝－6，3是解。

所以，该同余方程的解是x ≡－6，3（mod 15）且解数()15;f T ＝2。

【例3】求同余方程72742-+x x ≡0（mod 15）的解 （解）同样直接计算知4,1,2,7---=x 是解。

所以它的解是()15mod 4,1,2,7---≡x ，解数为4。

【例4】求解同余方程()15mod 092742≡-+x x 。

（解）经直接计算知，本方程无解，即解数为0。

说明：当()x f 的系数都是模m 的倍数时，显见，任意的整数值x 都是同余方程（1）的解，这样的同余方程 （1）的解数为m 。

但这并不是同余方程（1）的解数为m 的必要条件。

例如 215x ＋35x ＋14≡0（mod 7）显然，上方程等价于方程 0≡0（mod 7）【例5】由Fermat －Euler 定理知，同余方程 ()5mod 05≡-x x的解数为5；同余方程()7mod 07≡-x x的解数为7。

一般地，对素数p ，同余方程()p x x p mod 0≡-的解数为p 。

【例6】同余方程 ()()()()35mod 01112422≡+++-x x x x x即()35mod 0379≡--+x x x x的解数为35。

（证）记()x x f =1，()122-=x x f ，()123+=x x f ，()1244++=x x x f ，由同余的性质，()()()()35mod 01112422≡+++-x x x x x ⇔ ()()()()()()⎩⎨⎧≡+++-≡+++-7mod 01115mod 011124222422x x x x x x x x x x ⇔ 存在i ，j 使得()()⎩⎨⎧≡≡7mod 05mod 0x f x f j i 成立（因5、7都是素数）直接计算：()x f 1为奇函数，其余为偶函数x ＝0时，()01f ≡0（mod 5），()01f ≡0（mod 7） x ＝±1时，()x f 2≡0（mod 5），()x f 2≡0（mod 7）⇔()x f 2≡0（mod 35）即()x f i ＝()x f j ＝()x f 2x ＝±2时，()x f 3≡5≡0（mod 5），()x f 4≡21≡0（mod 7）即()x f i ＝()x f 3，()x f j ＝()x f 4x ＝±3时，()x f 3≡10≡0（mod 5），()x f 4≡91≡0（mod 7）x ＝±4时，()x f 2≡15≡0（mod 5），()x f 4≡273＝39·7≡0（mod 7）x ＝±5时，()x f 1≡±5≡0（mod 5），()x f 4≡651＝93·7≡0（mod 7）x ＝±6时，()x f 2≡35≡0（mod 35），x ＝±7时，()x f 3≡50≡0（mod 5），()x f 1≡±7≡0（mod 7）x ＝±8时，()x f 3≡65≡0（mod 5），()x f 2≡63≡0（mod 7）x ＝±9时，()x f 2≡80≡0（mod 5），()x f 4≡949·7≡0（mod 7）x ＝±10时，()x f 1≡±10≡0（mod 5），()x f 4≡1443·7≡0（mod 7）x ＝±11时，()x f 2≡24·5≡0（mod 5），()x f 4≡2109·7≡0（mod 7）x ＝±12时，()x f 2≡29·5≡0（mod 5），()x f 4≡2983·7≡0（mod 7）x ＝±13时， ()x f 3≡34·5≡0（mod 5），()x f 2≡24·7≡0（mod 7）x ＝±14时，()x f 2≡39·5≡0（mod 5），()x f 1≡±14≡0（mod 7）x ＝±15时， ()x f 1≡±15≡0（mod 5），()x f 2≡32·7≡0（mod 7）x ＝±16时， ()x f 2≡51·5≡0（mod 5），()x f 4≡9399·7≡0（mod 7）x ＝±17时， ()x f 3≡58·5≡0（mod 5），()x f 4≡11973·7≡0（mod 7）注意：由于本方程()35mod 0379≡--+x x x x 中x 的幂都是奇数，故当x 为其解释时，－x 也是其解。

(二) 同余方程的性质【定理3.1.1】（i ）若两个多项式f(x)≡g(x)（mod m ），则同余方程（1）的解和解数与同余方程g(x)≡0（mod m ）相同，此时称两个方程同解。

（ii ）若()1,=m a ，则同余方程（1）的解和解数与同余方程()()m x af mod 0≡相同。

特别地，当()1,=m a n 时，取a≡1-n a （mod m ），则多项式()x af 的首项系数为()m aa n mod 1≡ （证）（i ）显然。

（ii ）因为()1,=m a 时，有f (x)≡0（mod m ） ⇔a f (x)≡0（mod m ）（当(a,m)＝1时，b ≡c （mod m ）⇔ab ≡ac （mod m ））【例6】证明同余方程092742≡-+x x （mod 15）与方程632-+x x （mod 15）同解。

（证）首先92742-+x x ≡6342+-x x （mod 15），故方程092742≡-+x x （mod 15）与06342≡+-x x （mod15）同解。

其次，由于14-≡4（mod 15），所以，原方程又可以化简为14-(92742-+x x )≡0（mod 15）36108162-+x x ≡0（mod 15）632-+x x ≡0（mod 15）另外，同余方程093360223≡-++x x x （mod 12）与方程03323≡+-x x （mod 12）同解。

【定理3.1.2】（i ）设正整数d │m ，那么，模m 的同余方程（1）有解的必要条件是模d 的同余方程 ()()d x f mod 0≡ （2）有解。

（ii ）设方程（2）有解，它的全部解为s x x x ,,1Λ≡（mod d ） （3） 那么，对（1）的每个解（如果有的话）a ，有且仅有一个i x 满足a ≡i x （mod d ）（证）（i ）设a 是同余方程（1）的解，即f (a)≡0（mod m ）从而由同余性质知 m │f (a)。

已知m d |，所以d │f (a)所以 f (a)≡0（mod d ），即（2）成立。

（ii ）又若有两个解1x 和2x 同时满足a ≡1x （mod d ）， a ≡2x （mod d ） 则由同余的等价性之传递性知，必有1x ≡2x （mod d ）即（ii ）成立。

意义：方程（1）的解一定要在与方程（2）的解同余的数中去找。

如a 是（1）的解，i x 是（2）的解，则必有a ＝i x ＋kd ，其中k 为某个整数【例7】解同余方程()15mod 092742≡-+x x 。

（解）考虑模5的同余方程()5mod 092742≡-+x x （4）由于 ()5mod 12927422++-≡-+x x x x由定理3.1.1知，方程（4）与方程()5mod 0122≡++-x x 的解相同。

上式即 ()().5mod 212≡-x容易验证它无解。

因而由定理3.1.2知原同余方程无解。

【例8】解同余方程()9mod 09523≡++x x 。

（解）由直接计算知，同余方程()3mod 09523=++x x （即方程23x x -≡()x x x -2≡0（mod 3））有两个解：().3mod 1,0≡x方法一：利用方程23x x -≡0（mod 3）的解试探或穷举。

已知方程23x x -≡0（mod 3）的解为x ≡0,1（mod 3），故由定理3.1.2知原方程的不同的解一定在集合{0，3，6，1，4，7}中。

逐个试验：以x ≡0，3，－3，1，4，－2分别代入原方程中，可知x ≡－3，0，3，4满足原方程，而x ≡－2，1不满足原方程。