高次同余式的解数及解法

4.3高次同余式的解数及解法

本节初步讨论高次同余式的解数与解法：先把合数模的同余式化成质数模的同余式，然后通过下一节来解质数模的同余式。

A回顾与强调

二、同余式解的相关定理

上一节由孙子定理：设m1, m2, L, mk是正整数，

(mi, mj) = 1，m = m1m2Lmk ，Mi = ， MiMi＇ ≡ 1 (mod mi)，同余式组（同余方程组）(1) 的解为 (mod m)。反过来，解同余式 ，可将它化为同余式组 ，于是，有下面的定理

B重要定理证明的讲解

定理1设m = m1m2Lmk ，其中m1, m2, L, mk 是两两互素的正整数，f(x)是整系数多项式，则

A：同余式 f(x) ≡ 0 (mod m) （1） 与同余式组f(x) ≡ 0 (mod mi) （1 ≤ i ≤ k） （2） 等价；

B：以T与T（分别表示f(x) ≡ 0 (mod m)与f(x) ≡ 0 i1 ≤ i ≤ k）(mod mi) （1 ≤ i ≤ k）的解的个数，则T = T1T2…Tk 。 证明 A：设x0是适合（1）的解，即f(x0) ≡ 0 (mod m)，由整除的性质知

f(x0) ≡ 0 (mod mi) ，1 ≤ i ≤ k，

反之，设x0是适合（2）的解，即f(x0) ≡ 0 (mod mi) ，1 ≤ i ≤ k，则m1, m2, L, mk是两两互素的正整数知，f(x0) ≡ 0 (mod m)，故（1）

与（2）同解。

B：设同余方程(2)的全部解是 (mod mi)， （3）

即模mi有Ti个解，则同余方程组(2)等价于下面的T1T2…Tk个方程组：（4）

其中 通过式(3)中的数值，即通过同余方程(1)的全部解。

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

通过(3)式中的值时，由孙子定理的证明知所得到的T1T2…Tk个同余方程组(4)的解对于模m都是两两不同余的。证毕。

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

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

f(x) ≡ 0 (mod pα) (5) 的解，则它必是方程

f(x) ≡ 0 (mod pα-1) (6) 的解，因此，必有与x0相应的方程(6)的某个解x1，使

x0 ≡ x1 (mod pα-1)，x0 = x1 + pα-1t0，t0∈Z。

这提示我们：可以从方程(6)的解中去求方程(5)的解。于是，现在的问题是，对于方程(6)的每个解x1，是否必有方程(5)的解x0与之对应？若有，如何去确定它？

定理2 设p是素数，a≥ 2是整数，f(x) = anxn + L + a1x + a0是整系

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

(ⅰ) 若f＇(x1) ≡ 0 (mod p)，则存在整数t，使得 x = x1 + pα-1t (7) 是同余方程(5)的解。

(ⅱ) 若f＇(x1) ≡ 0 (mod p)，并且f(x1) ≡ 0 (mod pα)，则对于t = 0，1, 2, L, p - 1，式(7)中的x都是方程(5)的解。

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

f(x1+ pα-1t) =an(x1+ pα- 1t)n+an-1(x1+ pα-1t)n-1+L+a1(x1+ pα-1t)+a0 ≡ 0 (mod pα) (8)

利用泰勒展开式将f(x1+ pα-1t)在x1处展开得 f(x1) + pα-1t f＇(x1) ≡ 0 (mod pα)，

由于x1 是f(x) ≡ 0 (mod pα-1)的解(pα-1 |f(x1) ),上式两端同除

pα-1t f＇(x1) ≡ - (mod p) (9)

下面考虑两种情形。

(ⅰ) 若f＇(x) ≡ 0 (mod p)，则关于t的同余方程(9)有唯一解t ≡ t0 (mod p)，即t = t0 + pk（k∈Z）代入x = x1 + pα-1t得 x ≡ x1 + pα-1t0 (mod pα) 是同余方程(5)的解。

(ⅱ) 若f＇(x1) ≡ 0 (mod p)，并且f(x1) ≡ 0 (mod pα)，则式(5)对于任意的整数t成立，即同余方程(5)有p个解

t ≡ i (mod p)，0 ≤ i ≤ p - 1。

于是x ≡ x1 + pα-1i (mod pα)，0 ≤ i ≤ p - 1，都是同余方程(5)的解。证毕。

在定理中，没有对f＇(x1) ≡ 0 (mod p)并且 f(x1) ≡ 0 (mod pα)的情形进行讨论。事实上，此时，同余方程(6)无解。即，我们无法从同余方程(6)的解x1出发去求得同余方程(5)的解。 由定理，可以把解同余方程(5)，转化为解同余方程 f(x) ≡ 0 (mod p) (10)

事实上，由方程(10)的解，利用定理，可以求出方程f(x) ≡ 0 (mod p2)的解，再利用定理，又可以求出方程f(x) ≡ 0 (mod p3)的解，LL，直到求出方程(5)的解。

C总结

本节主要讲解了解把高次同余式划归为模pα的同余式，进一步划归为求模p的同余式（质数模的同余式）-化归思想。

D讲解例题

三、高次同余式解法举例

例1 解同余方程2x2 + 13x - 34 ≡ 0 (mod 53)。 解 容易验证，同余方程

2x2 + 13x - 34 ≡ 0 (mod 5) 有两个解x ≡ -1，2 (mod 5)。 (i)令x = -1 + 5t，代入同余方程

2x2 + 13 x - 34 ≡ 0 (mod 52)，

得到

2(-1 + 5t)2 + 13(-1 + 5t) - 34 ≡ 0 (mod 52)， -45 + 45t ≡ 0 (mod 52)，

9t ≡ 9 (mod 5)，t ≡ 1 (mod 5)，t = 1+ 5 t1。

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

x = -1 + 5(1 + 5t1) = 4 + 25t1，t1∈Z。

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

2(4 + 25t1)2 + 13(4 + 25t1) - 34 ≡ 0 (mod 53)， 50 + 725t1 ≡ 0 (mod 53)， 2 + 29t1 ≡ 0 (mod 5)， t1 ≡ 2 (mod 5)。

得到原同余方程的一个解

x = 4 + 25t1 = 4 + 25(2 + 5t2) ≡ 54 (mod 53)。

(ⅱ) 从同余方程的另一个解 x ≡ 2 (mod 5)出发利用上述方法，可以求出同余方程的另一个解。解略。 例2 解同余方程

x2 ≡ 1 (mod 2k)，k∈N。 (11) 解 若k = 1，则方程(11)的解是x ≡ 1 (mod 2)。

若k = 2，则方程(11)的解是x ≡ 1，-1 (mod 4)。 若k≥ 3，则同余方程(11)可化为

x2 - 1 = (x + 1)(x - 1) ≡ 0 (mod 2k)，

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

(2y + 2)2y ≡ 0 (mod 2k)，

y(y + 1) ≡ 0 (mod 2k-2) (12)

同余方程(12)的解是y1 ≡ 0，y2 ≡ -1 (mod 2k-2（)解数≤次数），即

y1 = 2k-2u， y2 = -1 + 2k-2v，u, v∈Z，

所以，方程(11)的解是

x1 = 2k-1u + 1，x2 = 2 k-1v - 1， u, v∈Z，

即

x ≡ 1，1 + 2 k-1，-1，-1 + 2 k-1 (mod 2k)。 这是由于u为偶数（u=0）时结果都为x ≡ 1 (mod 2k)； u为奇数时（u=1）时结果都为x ≡ 1 + 2 k-1 (mod 2k)；同理，v为偶数时x ≡ -1 (mod 2k)，v为奇数时x ≡ -1 + 2 k-1 (mod 2k)。 例3 解同余方程 x2 ≡ 2 (mod 73)。

解 设x是这个同余方程的解，把它可以表示成7进制数 x = x0 + 7x1 + 72x2，0 ≤ xi ≤ 6，0 ≤ i ≤ 2， 代入原方程，得到

(x0 + 7x1 + 72x2)2 ≡ 2 (mod 73)， (13) 因此

(x0 + 7x1 + 72x2)2 ≡ 2 (mod 7)， x02 ≡ 2 (mod 7)，

所以x0 ≡ 3或4 (mod 7)。于是x0 = 3或4（因为0 ≤ x0 ≤ 6）。

(ⅰ) 若x0 = 3，由式(13)，有

(3 + 7x1 + 72x2)2 ≡ 2 (mod 72)， 9 + 42x1 ≡ 2 (mod 72)，

注：分别剩余7的零次相和交叉相乘得到的7的一次相 6x1 ≡ -1 (mod 7)， x1 ≡ 1 (mod 7)，x1 = 1。 再由式(11)，有

(3 + 7×1 + 72x2)2 ≡ 2 (mod 73)， (10 + 72x2)2 ≡ 2 (mod 73)，

100+2×10×3x2 ≡ -1 (mod 7)，x2 ≡ 2 (mod 7)，x2 = 2。 这样，求得原同余方程的一个解是

x ≡ 3 + 7×1 + 72×2 = 108 (mod 73)。 (ⅱ) 若x0 = 4，用同样的方法求出另一个解。（略）。 例3中的方法是利用数的b进制表示，这一方法可以处理模bk的同余方程，而不必要求b是素数。

本文来源：https://www.bwwdw.com/article/iuna.html