初等数论同余方程

《初等数论同余方程》由会员分享，可在线阅读，更多相关《初等数论同余方程（36页珍藏版）》请在金锄头文库上搜索。

1、0第五章第五章 同余方程同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程 的解法。第一节第一节 同余方程的基本概念同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。 在本章中，总假定 m 是正整数。 定义定义 1 设 f(x) = anxn a1x a0是整系数多项式，称 f(x) 0 (mod m) (1) 是关于未知数 x 的模 m 的同余方程，简称为模 m 的同余方程。 若 an0 (mod m)，则称为 n 次同余方程。 定义定义 2 设 x0是整数，当 x = x0时式(1)成立，则称 x0是同余方程 (1)的解。凡对于模 m 同余的解，被视为同一个解。同

2、余方程(1)的解 数是指它的关于模 m 互不同余的所有解的个数，也即在模 m 的一个 完全剩余系中的解的个数。 由定义 2，同余方程(1)的解数不超过 m。 定理定理 1 下面的结论成立： () 设 b(x)是整系数多项式，则同余方程(1)与 f(x) b(x) b(x) (mod m) 等价； () 设 b 是整数，(b, m) = 1，则同余方程(1)与 bf(x) 0 (mod m) 等价； () 设 m 是素数，f(x) = g(x)h(x)，g(x)与 h(x)都是整系数多项式， 又设 x0是同余方程(1)的解，则 x0必是同余方程 g(x) 0 (mod m) 或 h(x) 0 (

3、mod m)1的解。 证明证明 留做习题。 下面，我们来研究一次同余方程的解。 定理定理 2 设 a，b 是整数，a0 (mod m)。则同余方程 ax b (mod m) (2) 有解的充要条件是(a, m)b。若有解，则恰有 d = (a, m)个解。 证明证明 显然，同余方程(2)等价于不定方程 ax my = b， (3) 因此，第一个结论可由第四章第一节定理 1 得出。 若同余方程(2)有解 x0，则存在 y0，使得 x0与 y0是方程(3)的解， 此时，方程(3)的全部解是，tZ。 (4) tmaayytmamxx),(),(00由式(4)所确定的 x 都满足方程(2)。记 d =

4、 (a, m)，以及 t = dq r，qZ，r = 0, 1, 2, , d 1， 则x = x0 qm (mod m)，0 r d 1。rdmxrdm0容易验证，当 r = 0, 1, 2, , d 1 时，相应的解dmdxdmxdmxx) 1(2 0000，L对于模 m 是两两不同余的，所以同余方程(2)恰有 d 个解。证毕。 在定理的证明中，同时给出了解方程(2)的方法，但是，对于具 体的方程(2)，常常可采用不同的方法去解。 例例 1 设(a, m) = 1，又设存在整数 y，使得 ab ym，则x (mod m)aymb 是方程(2)的解。 解解 直接验算，有 ax b ym b

5、(mod m)。2注注：例 1 说明，求方程(2)的解可以转化为求方程 my b (mod a) (5) 的解，这有两个便利之处：第一，将一个对于大模 m 的同余方程转 化为一个对于小模 a 的同余方程，因此有可能通过对模 a 的完全剩余 系进行逐个验证，以求出方程(5)和(2)的解；第二，设 m r (mod a)， r 0，且(a, m) = 1，a1是 m 对模 a 的最小非负剩余， 则同余方程a1x b(mod m) (7)am等价于同余方程(2)。解解 设 x 是(2)的解，则由 m = a1得到ama(mod m)，)(1ambamaxxamamxa即 x 是同余方程(7)的解。但

6、是由假设条件可知同余方程(2)与(7)都有 且只有一个解。所以这两个同余方程等价。 注注：用本例的方法，可以将同余方程(2)转化成未知数的系数更 小一些的同余方程，从而易于求解。 例例 4 解同余方程 6x 7 (mod 23)。 解解 由例 3，依次得到 6x 7 (mod 23) 5x 73 2 (mod 23) 3x 24 8 (mod 23)3 2x 8(7) 10 (mod 23) x 5 (mod 23)。 例例 5 设(a, m) = 1，并且有整数 0 使得 a 1 (mod m)， 则同余方程(2)的解是 x ba 1 (mod m)。 解解 直接验证即可。 注注：由例 5

7、及 Euler 定理可知，若(a, m) = 1，则 x ba(m) 1 (mod m) 总是同余方程(2)的解。 例例 6 解同余方程 81x3 24x2 5x 23 0 (mod 7)。 解解 原同余方程即是 3x3 3x2 2x 2 0 (mod 7)。 用 x = 0，1，2，3 逐个代入验证，得到它的解是 x1 1，x2 2，x3 2 (mod 7)。 注注：本例使用的是最基本的解同余方程的方法，一般说来，它的 计算量太大，不实用。 例例 7 解同余方程组。 (8) )7(mod232)7(mod153 yxyx解解 将(8)的前一式乘以 2 后一式乘以 3 再相减得到 19y 4

8、(mod 7)， 5y 4 (mod 7)， y 2 (mod 7)。 再代入(8)的前一式得到 3x 10 1 (mod 7)， x 4 (mod 7)。 即同余方程组(8)的解是 x 4，y 2 (mod 7)。 例例 8 设 a1，a2是整数，m1，m2是正整数，证明：同余方程组(9) )(mod)(mod2211 maxmax4有解的充要条件是 a1 a2 (mod (m1, m2)。 (10) 若有解，则对模m1, m2是唯一的，即若 x1与 x2都是同余方程组(9)的 解，则 x1 x2 (mod m1, m2)。 (11) 解解 必要性是显然的。下面证明充分性。 若式(10)成立

9、，由定理 2，同余方程 m2y a1 a2 (mod m1) 有解 y y0 (mod m1)，记 x0 = a2 m2y0，则 x0 a2 (mod m2) 并且 x0 = a2 m2y0 a2 a1 a2 a1 (mod m1)， 因此 x0是同余方程组的解。 若 x1与 x2都是方程组(9)的解，则 x1 x2 (mod m1)，x1 x2 (mod m2)， 由同余的基本性质，得到式(11)。习习 题题 一一1. 证明定理 1。 2. 解同余方程： () 31x 5 (mod 17)； () 3215x 160 (mod 235)。 3. 解同余方程组：。 )47(mod10)47(m

10、od3853 yxyx4. 设 p 是素数，0 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)是一个

11、次数为 n k 的整系数多项式，并且它的 xn k项的系 数是 an。 证明证明 由多项式除法，有 f(x) = (x x1)f1(x) r1， (2)15其中 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) 由于 x

12、2, , 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。 由定理

13、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 + 1xi (mod p)，1 i n，所以式(6)不能成立。这个矛| 盾说明同余方程(1)不能有 n 1 个解。证毕。 推论推论 若同余方程 bnxn b0 0 (mod p)的解数大于 n，则 pbi，0 i n。 （7) 证明证明 若式(7)不成立，设 p bd，d n，pbi， d 2，(a, p) = 1 的情形。此时，因为(4a, p) = 1，所以，方程(1)等 价于方程 4a2x2 4ab

14、x 4ac 0 (mod p)，19即 (2ax b)2 b2 4ac (mod p)。 这样，研究方程(1)归结为对方程 x2 n (mod p) (2) 的研究。 定义定义 给定整数 p，对于任意的整数 n，(n，p) = 1，若方程(2) 有解，则称 n 是模 p 的二次剩余，记为 nQR(p)；否则，称 n 是模 p 的二次非剩余，记为 nQNR(p)。 显然，若 n1 n2 (mod p)，则它们同是模 p 的二次剩余（或二次 非剩余） ，因此，在谈到模 p 的二次剩余（或二次非剩余）时，把 n1 和 n2看作是同一个。 以下，在本节中，总假定 p 是奇素数。 定理定理 若(n, p) = 1，则 () n 是模 p 的二次剩余的充要条件是 1 (mod p)；