解数的意思

高次同余式的解数及解法

4.3高次同余式的解数及解法本节初步讨论高次同余式的解数与解法:先把合

数模的同余式化成质数模的同余式，然后通过下一节来解质数模的同余式。

A回顾与强调

二、同余式解的相关定理

上一节由孙子定理:设m,m,L,m是正整数，12k

=，MM,?1(modm)，同余(m,m)=1，m=mmLm，Mij12kiiii式组(同

余方程组)(1)的解为(modm)。反过来，解同余式，可将它化为同余式组，于

是，有下面的定理

B重要定理证明的讲解定理1设m=mmLm，其中m,m,L,m是两两互素的

正整数，12k12k

f(x)是整系数多项式，则

A:同余式f(x)?0(modm)(1)与同余式组f(x)?0(modm)(1?i?k)

(2)i

等价;

B:以T与T(1?i?k)分别表示f(x)?0(modm)与f(x)?0i

(modm)(1?i?k)的解的个数，则T=TT…T。i12k证明A:设x0是适

合(1)的解，即f(x)?0(modm)，由整除的0

性质知

f(x)?0(modm)，1?i?k，0i

反之，设x是适合(2)的解，即f(x)?0(modm)，1?i?k，00i则m,m,

L,m是两两互素的正整数知，f(x)?0(modm)，故(1)12k0

与(2)同解。

B:设同余方程(2)的全部解是(modm)，(3)i

即模m有T个解，则同余方程组(2)等价于下面的TT…T个方程ii12k组:(4)

其中通过式(3)中的数值，即通过同余方程(1)的全部解。由孙子定理，对于

选定的每一组{}，同余方程组(4)对模m有唯一解，而当每个

通过(3)式中的值时，由孙子定理的证明知所得到的TT…T个同余12k方程组

(4)的解对于模m都是两两不同余的。证毕。

由定理4及算术基本定理，设，从而，解一般模的同余方程可以转化为解

模为素数幂的同余方程组。

α下面我们利用数学中的化归思想对模p的同余方程做进一步讨论容易看出，

若x是同余方程0

αf(x)?0(modp)(5)的解，则它必是方程

α-1f(x)?0(modp)(6)的解，因此，必有与x相应的方程(6)的某个解

x，使01

α-1α-1x?x(modp)，x=x+pt，t?Z。010100

这提示我们:可以从方程(6)的解中去求方程(5)的解。于是，现在的问题是，

对于方程(6)的每个解x，是否必有方程(5)的解x与之对应,10若有，如何去确定

它,

n定理2设p是素数，a?2是整数，f(x)=ax+L+ax+a是整系n10

数多项式，又设x是同余方程(6)的一个解。以f,(x)表示f(x)的导函1

数。

(?)若f,(x)?0(modp)，则存在整数t，使得1

α-1x=x+pt(7)1

是同余方程(5)的解。

α(?)若f,(x)?0(modp)，并且f(x)?0(modp)，则对于t=0，111,

2,L,p-1，式(7)中的x都是方程(5)的解。

α-1证明我们来说明，如何确定式(7)中的t，使x+pt满足同余方程

1(5)，即要使

α-1α-1nα-1n-1α-1f(x+pt)=a(x+pt)+a(x+pt)+L+a(x+pt)+a?0

1n1n-11110

α(modp)(8)

α-1利用泰勒展开式将f(x+pt)在x处展开得11

α-1αf(x)+ptf,(x)?0(modp)，11

α-1α-1由于x是f(x)?0(modp)的解(p|f(x)),上式两端同除11

α-1ptf,(x)?-(modp)(9)1

下面考虑两种情形。

(?)若f,(x)?0(modp)，则关于t的同余方程(9)有唯一解t?

kα-1t(modp)，即t=t+p(k?Z)代入x=x+pt得001

α-1αx?x+pt(modp)10

是同余方程(5)的解。

α(?)若f,(x)?0(modp)，并且f(x)?0(modp)，则式(5)11对于任意

的整数t成立，即同余方程(5)有p个解

t?i(modp)，0?i?p-1。

α-1α于是x?x+p(modp)，0?i?p-1，都是同余方程(5)的解。1i

证毕。

α在定理中，没有对f,(x)?0(modp)并且f(x)?0(modp)的情11

形进行讨论。事实上，此时，同余方程(6)无解。即，我们无法从同余方程(6)

的解x出发去求得同余方程(5)的解。1

由定理，可以把解同余方程(5)，转化为解同余方程

f(x)?0(modp)(10)

2事实上，由方程(10)的解，利用定理，可以求出方程f(x)?0(modp)

3的解，再利用定理，又可以求出方程f(x)?0(modp)的解，LL，直到求出

方程(5)的解。

C总结

α本节主要讲解了解把高次同余式划归为模p的同余式，进一步划归为求模p

的同余式(质数模的同余式)-化归思想。

D讲解例题

三、高次同余式解法举例

23例1解同余方程2x+13x-34?0(mod5)。解容易验证，同余方程

22x+13x-34?0(mod5)

有两个解x?-1，2(mod5)。

(i)令x=-1+5t，代入同余方程

222x+13x-34?0(mod5)，

得到

222(-1+5t)+13(-1+5t)-34?0(mod5)，

2-45+45t?0(mod5)，

9t?9(mod5)，t?1(mod5)，t=1+5t。1

于是，将t=1+5t代入x=-1+5t得到1

x=-1+5(1+5t)=4+25t，t?Z。111

将上式的x代入原同余方程得到

232(4+25t)+13(4+25t)-34?0(mod5)，11

350+725t?0(mod5)，1

2+29t?0(mod5)，1

t?2(mod5)。1

得到原同余方程的一个解

3x=4+25t=4+25(2+5t)?54(mod5)。12

(?)从同余方程的另一个解x?2(mod5)出发利用上述方法，可以求出同余

方程的另一个解。解略。

例2解同余方程

kx2?1(mod2)，k?N。(11)

解若k=1，则方程(11)的解是x?1(mod2)。

若k=2，则方程(11)的解是x?1，-1(mod4)。

若k?3，则同余方程(11)可化为

2kx-1=(x+1)(x-1)?0(mod2)，

的解必是奇数，设x=2y+1，则同余方程(11)成为

k(2y+2)2y?0(mod2)，

k-2y(y+1)?0(mod2)(12)

k-2同余方程(12)的解是y?0，y?-1(mod2(解数?次数)，)21

即

k-2k-2y=2u，y=-1+2v，u,v?Z，12

所以，方程(11)的解是

k-1k-1x=2u+1，x=2v-1，u,v?Z，12

即

k-1k-1kx?1，1+2，-1，-1+2(mod2)。

k这是由于u为偶数(u=0)时结果都为x?1(mod2);u为奇数时

k-1k(u=1)时结果都为x?1+2(mod2);同理，v为偶数时x?-1

kk-1k(mod2)，v为奇数时x?-1+2(mod2)。

3例3解同余方程x?2(mod7)。2

解设x是这个同余方程的解，把它可以表示成7进制数

2x=x+7x+7x，0?x?6，0?i?2，012i

代入原方程，得到

223(x+7x+7x)?2(mod7)，012

(13)

因此

22(x+7x+7x)?2(mod7)，012

2x?2(mod7)，0

所以x?3或4(mod7)。于是x=3或4(因为0?x?6)。000

(?)若x=3，由式(13)，有0

222(3+7x+7x)?2(mod7)，12

229+4x?2(mod7)，1

注:分别剩余7的零次相和交叉相乘得到的7的一次相

6x?-1(mod7)，1

=1。x?1(mod7)，x11

再由式(11)，有

223(3+7×1+7x)?2(mod7)，2

223(10+7x)?2(mod7)，2

100+2×10×3x?-1(mod7)，x?2(mod7)，x=2。222

这样，求得原同余方程的一个解是

23x?3+7×1+7×2=108(mod7)。

(?)若x=4，用同样的方法求出另一个解。(略)。0

例3中的方法是利用数的b进制表示，这一方法可以处理模kb的同余方程，

而不必要求b是素数。