05同余方程(编辑修改稿)

05同余方程(编辑修改稿)内容摘要：

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 解同余方程 120 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)，即 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。 这样，求得原同余方程的一个解是 121 x  3  71  722 = 108 (mod 73)。 (ⅱ ) 若 x0 = 4，用同样的方法求出另一个解。 （略）。 注 ：例 4 中的方法是利用数的 b进制表示，这一方法可以处理模bk的同余方程，而不必要求 b是素数。 习 题 三 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 的同余方程的求解。 本节要对素数模的同余方程做些初步研究。 以下，设 f(x) = anxn    a1x  a0是整系数多项式， p是素数，p| an。 定理 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) 122 两边令 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) 由于 x2,  , xk对于模 p是两两不同余的，所以，上式给出 f1(xi)  0 (mod p)， i = 2,  , k。 (5) 由此及归纳法，即可证明定理。 证毕。 推论 若 p是素数，则对于任何整数 x，有 x p  1  1  (x  1)(x  2) (x  p  1) (mod p)。 证明 由 Fermat定理（第二章第四节定理 2），数 1, 2,  , p  1是同余方程 x p  1  1 (mod p) 的解，因此，利用定理 1即可得证。 定理 2 同余方程 (1)的解数  n。 证明 假设同余方程 (1)有 n + 1个不同的解 x  xi (mod p)， 1  i  n  1。 由定理 1，有 f(x)  an(x  x1) (x  xn) (mod p)，因此 0  f(xn + 1)  an(xn + 1  x1) (xn + 1  xn) (mod p)。 (6) 由于 p| an， xn + 1 xi (mod p)， 1  i  n，所以式 (6)不能成立。 这个矛盾说明同余方程 (1)不能有 n  1个解。 证毕。 推论 若同余方程 bnxn    b0  0 (mod p)的解数大于 n，则 pbi， 0  i  n。 （ 7) 证明 若式 (7)不成立，设 p| bd， d  n， pbi， d j  n。 则 bnxn    b0  bdxd    b0  0 (mod p)。 (8) 由定理 2，同余方程 (8)的解数不大于 d，因而不大于 n，这与假设矛盾。 因此，式 (7)必成立。 证毕。 定理 3 同余方程 (1)或者有 p个解，或者存在次数不超过 p  1的整系数多项式 r(x)，使得同余方程 (1)与 r(x)  0 (mod p)等价。 证明 由多项式除法可知，存在整系数多项式 g(x)与 r(x)，使得 f(x) = g(x)(x p  x)  r(x)。 (9) 123 由 Fermat定理，对于任意的整数 x，有 x p  x (mod p)，因此，如果 r(x)的系数都是 p的倍数，则对于任意的整数 x， f(x)  0 (mod p)，即同余方程 (1)有 p个解。 如果 r(x)的系数不都是 p的倍数，则 r(x)的次数不超过 p  1。 由式 (9)看出，对于任意的整数 x， f(x)  r(x) (mod p)，即同余方程 (1)与 r(x)  0 (mod p)等价。 证毕。 定理 4 设 n  p，则同余方程 f(x) = xn  an  1xn  1    a1x  a0  0 (mod p) (10) 有 n个解 的充要条件是存在整数多项式 q(x)和 r(x)， r(x)的次数 n，使得 x p  x = f(x)q(x)  pr(x)。 (11) 证明 必要性 由多项式除法，存在整系数多项式 q(x)与 r1(x)，r1(x)的次数 n，使得 x p  x = f(x)q(x)  r1(x)。 (12) 若同余方程 (10)有 n个解 x  xi (mod p)（ 1  i  n），则由式 (12)和Fermat定理，得到 r1(xi)  0 (mod p)， 1  i  n。 由此及定理 2推论，可知 r1(x)的系数都能被 p整除，即 r1(x) = pr(x)， 其中 r(x)是整系数多项式。 这证明了式 (11)。 充分性 若式 (11)成立，由 Fermat定理，对于任何整数 x，有 0  x p  x  f(x)q(x) (mod p)， (13) 即同余方程 f(x)q(x)  0 (mod p) 有 p个解，但是， q(x)是 p  n次多项式，所以由定理 2，方程 q(x)  0 (mod p)的解数  p  n。 以 表示同余方程 (10)的解数，则由第一节定理 1，有  + p  n  p，   n， 再利用定理 2，得到  = n。 证毕。 注 ：若 p| an，由辗转相除法可求出 an， p| an使得 anan  1 (mod p)，于是，同余方程 (1)与同余方程 anf(x) = xn  anan  1xn  1    ana1x  ana0 (mod p) 等价。 因此，定理 4是有普遍性的。 定 理 5 若 p是素数， np  1， p| a则 124 x n  a (mod p) (14) 有解的充要条件是 npa1 1 (mod p)。 (15) 若有解，则解数为 n。 证明 必要性 若方程 (14)有解 x0，则 p| x0，由 Fermat定理，得到 npnnp xa 101 )(   = x0p  1 1 (mod p)。 充分性 若式 (15)成立，则 ，)1()()()1)((11111npnnpnpnpnpaxxPaxaaxxxx 其中 P(x)是关于 x 的整系数多项式。 由定理 4 可知同余方程 (14)有 n个解。 证毕。 例 1 判定同余方程 2x3  3x  1  0 (mod 7)是否有三个解。 解 因为 24  1 (mod 7)，所以，原方程与 42x3  43x  4  0 (mod 7) 即 x3  2x  3  0 (mod 7) 等价。 由于 x7  x = ( x3  2x  3)(x4  2x2  3x  4)  12x2  16x  12， 所以，由定理 4可知，原方程的解数小于 3。 例 2 解同余方程 3x14  4x10  6x  18  0 (mod 5)。 解 由 Fermat定理， x5  x (mod 5)， 因此，原同余方程等价于 2x2  x  3  0 (mod 5)。 (16) 将 x  0， 1， 2 (mod 5)分别代入方程 (16)进行验证，可知这个同余 方程解是 x  1 (mod 5)。 125 习 题 四 1. 解同余方程： (ⅰ ) 3x11  2x8  5x4  1  0 (mod 7)； (ⅱ ) 4x20  3x12  2x7  3x  2  0 (mod 5)。 2. 判定 (ⅰ ) 2x3  x2  3x  1  0 (mod 5)是否有三个解； (ⅱ ) x6  2x5  4x2  3  0 (mod 5)是否有六个解。 3. 设 (a。