此处，t0是某个适当的整数。
这提示我们：可以从方程(2)的解中去求方程(1)的解。于是，现在的问题是，对于方程(2)的每个解x1，是否必有方程(1)的解x0与之对应？若有，如何去确定它？
定理 设p是素数，? ? 2是整数，f(x) = anxn ? ? ? a1x ? a0是整系数多项式，又设x1是同余方程(2)的一个解。以f ?(x)表示f(x)的导函数。 (ⅰ) 若f ?(x1)??0 (mod p)，则存在整数t，使得
x = x1 ? p ? ? 1t (3)
是同余方程(1)的解。
(ⅱ) 若f ?(x1) ? 0 (mod p)，并且f(x1) ? 0 (mod p ?)，则对于t = 0，1, 2, ?, p ? 1，式(3)中的x都是方程(1)的解。
证明 我们来说明，如何确定式(3)中的t，使x1 ? p? ? 1t满足同余方程(1)，即要使
an(x1+p? ? 1t)n+an ? 1(x1+p? ? 1t)n ? 1+?+a1(x1+p? ? 1t)+a0 ? 0 (mod p?)， (4) 即
f(x1) ? p ? ? 1tf ?(x1) ? 0 (mod p ?)，
f(x1)tf ?(x1) ? ???(mod p)。 (5)
p1下面考虑两种情形。 (ⅰ) 若f ?(x)??0 (mod p)，则关于t的同余方程(5)有唯一解t ? t0 (mod p)，即t = t0 ? pk（k?Z），于是
x ? x1 ? p? ? 1t0 (mod p?)
是同余方程(1)的解。
(ⅱ) 若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，都是同余方程(1)的解。证毕。
?在定理中，没有对f ?(x1) ? 0 (mod p)并且 f(x1)??0 (mod p)的情形进行讨论。事实上，此时，同余方程(5)无解。即，我们无法从同余方程(2)的解x1出发去求得同余方程(1)的解。
由定理，可以把解同余方程(1)，转化为解同余方程
f(x) ? 0 (mod p)。 (6)
117
事实上，由方程(6)的解，利用定理，可以求出方程f(x) ? 0 (mod p2)的解，再利用定理，又可以求出方程f(x) ? 0 (mod p3)的解，??，直到求出方程(1)的解。
推论 使用定理的记号，
(ⅰ) 若x ? a (mod p)是同余方程(6)的解，并且f ?(a)??0 (mod p)，则存
?在x?，x? ? a (mod p)，使得x ? x? (mod p)是同余方程(1)的解。
(ⅱ) 若f ?(x) ? 0 (mod p)与同余方程(6)没有公共解，则对于任意的整数? ? 1，同余方程(1)与(6)的解数相同。 证明 留做习题。 例1 解同余方程
x3 ? 3x ? 14 ? 0 (mod 45)。
解 原同余方程等价于同余方程组
x3 ? 3x ? 14 ? 0 (mod 9)， (7) x3 ? 3x ? 14 ? 0 (mod 5)。 (8)
先解同余方程(7)。容易验证，同余方程x3 ? 3x ? 14 ? 0 (mod 3)的解是x ? 2 (mod 3)。
令x = 2 ? 3t并代入方程(7)，得到
(2 ? 3t)3 ? 3(2 ? 3t) ? 14 ? 0 (mod 9)， (9)
容易看出，这是一个对于任何整数t都成立的同余式，所以，方程(9)的解是t ? 0，1，2 (mod 3)，于是方程(7)的解是
x ? 2，5，8 (mod 9)。 (10)
再解同余方程(8)。用x = 0，1，2，3，4去验证，得到(8)的解是
x ? 1，2 (mod 5)。
因此，原同余方程的解是下面六个同余方程组的解： x ? a1 (mod 9)， a1 = 2，5，8， x ? a2 (mod 5)， a2 = 1，2。
利用孙子定理解这六个方程组，记
m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9，M1? = 2，M2? = ?1， 则
x ? 10a1 ? 9a2 (mod 45)。
将a1和a2的不同取值代入，得到所求的解是 x1 ? 10?2 ? 9?1 ? 11 (mod 45)， x2 ? 10?2 ? 9?2 ? 2 (mod 45)， 118
x3 ? 10?5 ? 9?1 ? 41 (mod 45)， x4 ? 10?5 ? 9?2 ? 32 (mod 45)， x5 ? 10?8 ? 9?1 ? 26 (mod 45)， x6 ? 10?8 ? 9?2 ? 17 (mod 45)。 例2 解同余方程
2x2 ? 13x ? 34 ? 0 (mod 53)。 (11)
解 容易验证，同余方程
2x2 ? 13x ? 34 ? 0 (mod 5) (12)
有两个解x ? ?1，2 (mod 5)。 令
x = ?1 ? 5t， (13)
代入同余方程
2x2 ? 13 ? 34 ? 0 (mod 52)， (14)
得到
2(?1 ? 5t)2 ? 13(?1 ? 5t) ? 34 ? 0 (mod 25)，
?45 ? 45t ? 0 (mod 25)，
9t ? 9 (mod 5)，t ? 1 (mod 5)。 (15)
于是，将式(15)与式(13)联合，得到方程(14)的解
x = ?1 ? 5(1 ? 5t1) = 4 ? 25t1，t1?Z。 (16)
将式(16)中的x代入同余方程(11)，得到
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)。
将上式与(16)联合，得到同余方程(11)的一个解
x = 4 ? 25t1 = 4 ? 25(2 ? 5t2) ? 54 (mod 53)。
(ⅱ) 从同余方程(12)的另一个解 x ? 2 (mod 5)出发利用上述方法，可以求出同余方程(11)的另一个解。（略，请读者补足）。 例3 解同余方程
x2 ? 1 (mod 2k)，k?N。 (17)
解 若k = 1，则方程(17)的解是x ? 1 (mod 2)。 若k = 2，则方程(17)的解是x ? 1，?1 (mod 4)。 若k ? 3，则同余方程(17)，即
119
x2 ? 1 = (x ? 1)(x ? 1) ? 0 (mod 2k)，
的解必是奇数，设x = 2y + 1，则同余方程(1)成为
(2y ? 2)2y ? 0 (mod 2k)，
y(y ? 1) ? 0 (mod 2k ? 2)。 (18)
同余方程(18)的解是y1 ? 0，y2 ? ?1 (mod 2k ? 2)，即
y1 = 2k ? 2u， y2 = ?1 ? 2k ? 2v，u, v?Z，
所以，方程(17)的解是
x1 = 2k ? 1u ? 1，x2 = 2k ? 1v ? 1， u, v?Z，
即
x ? 1，1 ? 2k ? 1，?1，?1 ? 2k ? 1 (mod 2k)。
例4 解同余方程 x2 ? 2 (mod 73)。
解 设x是这个同余方程的解，则它可以表示成
x = x0 ? 7x1 ? 72x2，0 ? xi ? 6，0 ? i ? 2，
代入原方程，得到
(x0 ? 7x1 ? 72x2)2 ? 2 (mod 73)， (19)
因此
(x0 ? 7x1 ? 72x2)2 ? 2 (mod 7)，
x02 ? 2 (mod 7)，
所以x0 ? 3或4 (mod 7)。于是x0 = 3或4。 (ⅰ) 若x0 = 3，由式(19)，有
(3 ? 7x1 ? 72x2)2 ? 2 (mod 72)，
9 ? 42x1 ? 2 (mod 72)， 6x1 ? ?1 (mod 7)， x1 ? 1 (mod 7)，x1 = 1。
再由式(19)，有
(3 ? 7?1 ? 72x2)2 ? 2 (mod 73)， (10 ? 49x2)2 ? 2 (mod 73)，
3x2 ? ?1 (mod 7)，x2 ? 2 (mod 7)，x2 = 2。
这样，求得原同余方程的一个解是
x ? 3 ? 7?1 ? 72?2 = 108 (mod 73)。
(ⅱ) 若x0 = 4，用同样的方法求出另一个解。（略）。
注：例4中的方法是利用数的b进制表示，这一方法可以处理模bk的同余方程，而不必要求b是素数。 120
习 题 三
1. 证明定理的推论。
2. 将例2中略去的部分补足。 3. 将例4中略去的部分补足。 4. 解同余方程x2 ? ?1 (mod 54)。
5. 解同余方程f(x) = 3x2 ? 4x ? 15 ? 0 (mod 75)。
6. 证明：对于任意给定的正整数n，必存在m，使得同余方程x2 ? 1 (mod m)的解数T > n。
第四节 素数模的同余方程
在上节中，我们证明了，对于素数p，模p?的同余方程的求解可以转化为模p的同余方程的求解。本节要对素数模的同余方程做些初步研究。
|an。以下，设f(x) = anxn ? ? ? a1x ? a0是整系数多项式，p是素数，p?
定理1 设k ? n，若同余方程
f(x) = anxn ? ? ? a1x ? a0 ? 0 (mod p) (1)
有k个不同的解x1, x1, ?, xk，则对于任意的整数x，有
f(x) ? (x ? x1) (x ? x2)?(x ? xk)fk(x) (mod p)，
其中fk(x)是一个次数为n ? k的整系数多项式，并且它的xn ? k项的系数是an。
证明 由多项式除法，有
f(x) = (x ? x1)f1(x) ? r1， (2)
其中f1(x)是首项系数为an的n ? 1次整系数多项式，r1是常数。在式(2)两边令x = x1，则由假设条件可知f(x1) = r1 ? 0 (mod p)，因此，式(2)成为
f(x) ? (x ? x1)f1(x) (mod p)。 (3)
因此，当k = 1时，定理成立。如果k > 1，在上式中，令x = xi（i = 2, 3, ?, k），则有
0 ? f(xi) ? (xi ? x1)f1(xi) (mod p)。 (4)
121