3 高次同余式的解数及解法(精选、)

§3 高次同余式的解数及解法

定理1 若m1,,mk是k个两两互质的正整数，mm1mk,则同余式

fx0modm （1）

与同余式组

fx0modm1,fx0modm2, （2） fx0modmk等价。

以T表示同余式（1）的解数，以Ti表示同余式fx0modmi的解数，i1,则

,k,TT1Tk.

证 （ⅰ）先证（1）和（2）等价。

设x0是适合（1）的任一整数，则fx00modm.因mi|m,i1,,k,故

fx00modmi,i1,故x0也适合（2）。

,k

反之，设x0为适合（2）的任一整数，则

fx00modm1,fx00modm2, fx0modm0k但m1,,mk两两互质，m1,,mkm1mkm.故

fx00modm,

即x0也适合（1）。

（ⅱ）设fx0modmi对模mi的Ti个解为

xbi1,bi2,

,biTimodmi

116 / 8116

word.

则同余式组（2）的解为下列诸同余式组

xb1t1modm1,xb2t2modm2, （3） xbmodmktkk的解，其中ti1,2,对模m恰有一解

,Ti,i1,2,,k.由孙子定理得，对于每一组t1,t2,,tk，同余式组（3）

xxt1t2由上节定理2得，

tkmodm.

,Ti,i1,2,,k

Tk.故TTT12Tk.

xxt1t2tkmodm,ti1,2,为同余式（1）对模m的所有不同的解，个数恰为TT12例1 解同余式

fx0mod35,fxx42x38x9 （4）

解 同余式（4）等价于同余式组

fx0mod5, （5 ） fx0mod7可以验证同余式组（5）的第一个同余式的解为

x1,4mod5.

同余式组（5）的第二个同余式的解为

x3,5,6mod7.

故同余式（4）有236个解。由孙子定理，可得同余式组

xb1mod5, xb2mod7为

x21b115b2mod35,

其中，b11,4,b23,5,6.于是可得同余式（4）的全部解为

x31,26,6,24,19,34mod35.

设m的标准分解式为mp11p2

2pkk,则同余式

117 / 8117

word.

fx0modm

与同余式组

fx0modp11,fx0modp22, kfx0modpk等价。

故应讨论同余式

fx0modp （6） 的解法。

易知，适合（6）的整数x必适合

fx0modp. （7）

下面考虑如何从同余式（7）的解求出同余式（6）的解。

定理2 设

xx1modp （8）

是同余式（7）的一个解，p/|fx1，则（8）恰好含有同余式（6）的一个解

xxmodp,

其中，xx1modp. 证 对作数学归纳法。

（ⅰ）先证当2时，命题结论是正确的。 由（8）， xx1pt,t0,1,2,将它代入

（9）

fx0modp2

得

fx1pt10modp2,fx1pt1fx10modp2



x1pt1kx1kkpt1x1k1modp2.但fx10modp,故

118 / 8118

word.

t1fx1因p/|fx1,故对模p恰有一解

fx1modp. pt1t1modp

即

t1t1pt2,t20,1,2,

代入（9）得，（8）中满足fx0modp2的全部整数是

xx1pt1pt2x2p2t2,t20,1,2,其中，x2x1pt1.

故（8）恰好含有fx0modp2的一个解



xx2modp2,

其中，x2x1modp. 其中，x2x1modp.

假设定理结论对13成立，即（8）恰含有

fx0modp1

的一个解xx1modp1，即（8）中满足fx0modp1的全部整数是

xx1p1t1,t10,1,2,

其中，x1x1modp.代入（6）得

fx1p1t1fx10modp

x1p1t1x1kkp1t1x1k1modp

k但fx10modp1，故

t1fx1fx1modp. p1又x1x1modp,故fx1fx1modp.而p/fx1,从而p/fx1,故

119 / 8119

word.

上式恰有一解

t1t1modp,即

t1t1pt,t0,1,2,

故（8）中满足同余式（6）的全部整数是

xx1p1t1ptxpt,t0,1,2,其中，xx1p1

t1x1x1modp.故（8）恰好给出了同余式（6）的一个解

xxmodp,

其中xx1modp.

例2 解同余式

fx0mod27,fxx47x4.

解 经过验算，fx0mod3有一解x1mod3.又3/f1,以x13t1代入

fx0mod9得

f13t1f10mod9. （10）

因f13mod9,f12mod9,故（10）等价于

33t120mod3,t113t2.

于是，x1313t249t2是 fx0mod9的一解。以x49t2代入

fx0mod27得

f49t2f40mod27,189t2200mod27,2t220mod3,t223t3,x4923t32227t3.故x22mod27为同余式的解。 习题 1. 解同余式

120 / 8120

word.

6x327x217x200(mod30). （1）

解 因30235, 且2,3,5两两互质，故同余式（1）与同余式组

6x327x217x200(mod2),326x27x17x200(mod3), （2） 6x327x217x200(mod5)同解。容易验证，同余式组（2）的第一个同余式有两个解：即

x0,1(mod2),

第二个同余式有一个解：即

x2(mod3), 第三个同余式

x0,1,2(mod5). 故同余式（1）有2136个解。即诸同余式组

xb1(mod2),xb2(mod3),xb3(mod5),b10,1,b22,b30,1,2

的解。由孙子定理得

x15b110b26b3(mod30).

以b1,b2,b3的值分别代入即得（1）的全部解：

x20,26,2,5,11,17(mod30).

2. 解同余式

31x457x396x1910(mod225). （1）

解 因22535,(3,5)1,故同余式（1）与同余式组

43231x57x96x1910(mod3), （2） 43231x57x96x1910(mod5)2222同解。

设f(x)31x57x96x191，则f(x)124x171x96.通过验证，易得同余式

4332f(x)0(mod3)

共有两个解：x1,1(mod3).

因f(1)391不是3的倍数，故x13t1(t10,1,2,121 / 8121

)中含有同余式组(2)的第

word.

一个同余式的一个解。以x13t1代入同余式组(2)的第一个同余式，得

f(1)mod3, 3391t1125(mod3),t11(mod3),t113t2(t20,1,2,).f(1)3t1f(1)0(mod9),t1f(1)故x13(13t2)49t2即x4(mod9)为同余式组(2)的第一个同余式的一个解。 因f(1)143不是3的倍数，故x13t1(t10,1,2,)中含有同余式组(2)

的第一个同余式的一个解。以x13t1代入同余式组(2)的第一个同余式，得

f(1)mod3, 3143t123(mod3),t12(mod3),t123t2(t20,1,2,).f(1)3t1f(1)0(mod9),t1f(1)故x13(23t2)59t2即x5(mod9)为同余式组(2)的第一个同余式的一个解。 因此，同余式组(2)的第一个同余式共有两个解：x4,5(mod9).

通过验证，易得同余式

f(x)0(mod5)

共有两个解：x1,2(mod5).

因f(1)391不是5的倍数，故x15t1(t10,1,2,)中含有同余式组(2)的第

二个同余式的一个解。以x15t1代入同余式组(2)的第二个同余式，得

f(1)mod5, 5391t175(mod5),t10(mod5),t15t2(t20,1,2,).f(1)5t1f(1)0(mod25),t1f(1)故x155t2125t2即x1(mod25)为同余式组(2)的第二个同余式的一个解。 因f(2)1772不是5的倍数，故x25t1(t10,1,2,)中含有同余式组(2)的

第二个同余式的一个解。以25t1代入同余式组(2)的第二个同余式，得

f(2)5t1f(2)0(mod25)，但f(2)10(mod25)，故

105t1f(2)0(mod25),2t1f(2)0(mod5),1722t12(mod5),t11(mod5),t115t2(t20,1,2,).122 / 8122

word.

故x2515t2325t2即x3(mod25)为同余式组(2)的第二个同余式的一个解。

因此，同余式组(2)的第二个同余式共有两个解：x1,3(mod25). 故同余式（1）有224个解。即诸同余式组

xb1(mod9),xb2(mod25),b14,5,b21,3

的解。由孙子定理得

x100b199b2(mod225).

以b1,b2的值分别代入即得（1）的全部解：

x76,22,176,122(mod225).

最新文件---------------- 仅供参考--------------------已改成word文本 --------------------- 方便更改

123 / 8123