奇素数模的二次同余方程的具体解法-Java在线实施

前面两节解决了奇素数模二次同余方程

有无解的判定问题，本节考虑这类同余方程的具体求解问题.由于p是奇素数，故p满足且仅满足下列同余式之一：

p≡1（mod8），p≡3（mod8），p≡5（mod8），p≡7（mod8）.

下面对上述情形逐一加以讨论.

命题6.5.1　设p是奇素数，a∈Z且　若p≡3（mod8）或p≡7（mod8），则（6.5.1）的解为

证明　由定理6.3.2（1）知于是由

p≡3（mod8）或p≡7（mod8）

知是偶数，故这表明是该方程的解.由于p是奇素数且（a，p）=1，从而故是两个不同的解.据定理6.2.5，这就是该方程的全部解.证毕.

例6.5.2　解同余方程x2≡11（mod43）.

解　由　知该方程有解.注意到43≡3（mod8），据命题6.5.1，该同余方程的解为由113=1331≡-2（mod43）知119≡-8（mod43）.从而

1111≡-8×112≡-968≡-22（mod43）.

这表明该同余方程的解为x≡±22（mod43）.解毕.

命题6.5.3　设p是奇素数，a∈Z，p≡5（mod8）且　则

有且只有一个成立.若前者成立，则（6.5.1）的解为若后者成立，则（6.5.1）的解为

证明　由定理6.3.2（1）及事实　知由p≡5（mod8）知是偶数，从而，即由p是素数知或若两个整除关系同时成立，则有但这是不可能的，因为p是奇素数且（a，p）=1.于是

中有且只有一个成立.若前者成立，则

由p≡5（mod8）知是偶数，从而

类似于命题6.5.1可以证明，

是（6.5.1）的全部解.若后者成立，则

由p≡5（mod8）知是偶数且

据定理6.3.2（1），有

故

类似于命题6.5.1，可以证明

是（6.5.1）的全部解.证毕.

例6.5.4　解同余方程x2≡29（mod149）.

解　首先，有149≡5（mod8）且　由

294=707281≡-22（mod149）和224=234256≡28（mod149）

知

229≡（224）2×22≡282×22≡39×22=858≡-36（mod149）

和(www.xing528.com)

2937=（294）9×29≡（-22）9×29≡36×29≡1044≡1（mod149）.

这说明该方程是命题6.5.3中的前一情形.注意到

该方程的解是x≡±25（mod149）.解毕.

例6.5.5　解同余方程x2≡23（mod101）.

解　易见101≡5（mod8），由232≡24（mod101）和242≡-30（mod101）知

故有

和

这说明该方程是命题6.5.3中的后一情形.注意到210≡1024≡14（mod101），有

220≡142=196≡-6（mod101）

和

225=220·25≡（-6）×32≡10（mod101）.

于是该方程的解是x≡±10×49≡±86（mod101）.解毕.

上面考虑了p≡3（mod8），p≡5（mod8）和p≡7（mod8）三种情形.遗憾的是，对p≡1（mod8）的情形，没有类似于上述三种情形的一般结论.下面仅通过两个例子来展示这类同余方程的解法.

例6.5.6　解同余方程x2≡73（mod137）.

解　由　知该方程有解.据定理6.3.2（1），有由137是奇素数知7334≡1（mod137）和7334≡-1（mod137）有且只有一个成立.下面说明前者成立.由

732=5329=39×137-14≡-14（mod137）

知7334≡-1417（mod137）.由143=2744=137×20+4≡4（mod137）知

1417=1415·142≡45·196≡65·59≡3835≡-1（mod137）.

这表明7334≡-1417≡1（mod137）.再根据137是奇素数知7317≡1（mod137）和7317≡-1（mod137）有且只有一个成立.实际上，经过类似于上面的讨论可得7317≡1（mod137）.故7318≡73（mod137）.这表明（739）2≡73（mod137）.于是该方程的解为x≡±739≡±22（mod137）.解毕.

例6.5.7　解同余方程x2≡19（mod137）.

解　由　知该方程有解.据定理6.3.2（1），有

由137是奇素数知1934≡1（mod137）和1934≡-1（mod137）有且只有一个成立.下面说明后者成立.由193=6859=137×50+9≡9（mod137）知

而由94=6561=137·48-15≡-15（mod137）知98≡（-15）2≡-49（mod137）.注意到93=729=5·137+44≡44（mod137），有

故

另一方面，由

知3是模137的二次非剩余.由定理6.3.2（1）知

故368·1934≡1（mod137）.这表明334·1917≡1（mod137）和334·1917≡-1（mod137）有且仅有一个成立.易证334·1917≡1（mod137）成立.故334·1918≡19（mod137）.即（317·199）2≡19（mod137）.这说明

就是该方程的两个解.解毕.