初等数论第五章同余方程

107 第五章 同余方程 本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。 第一节 同余方程的基本概念 本节要介绍同余方程的基本概念及一次同余方程。 在本章中，总假定m 是正整数。 定义1 设f(x) = anxn    a1x  a0 是整系数多项式，称 f(x)  0 (mod m) (1) 是关于未知数x 的模m 的同余方程，简称为模m 的同余方程。 若an 0 (mod m)，则称为n 次同余方程。 定义2 设x0 是整数，当x = x0 时式(1)成立，则称x0 是同余方程(1)的解。凡对于模m 同余的解，被视为同一个解。同余方程(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 (mod m) 108 的解。 证明 留做习题。 下面，我们来研究一次同余方程的解。 定理 2 设 a，b 是整数，a  0 (mod m)。则同余方程 ax  b (mod m) (2) 有解的充要条件是(a, m)b。若有解，则恰有 d = (a, m)个解。 证明 显然，同余方程(2)等价于不定方程 ax  my = b， (3) 因此，第一个结论可由第四章第一节定理 1 得出。 若同余方程(2)有解x 0，则存在 y 0，使得 x 0 与 y 0 是方程(3)的解，此时，方程(3)的全部解是 tmaayytmamxx),(),(00，tZ。 (4) 由式(4)所确定的x 都满足方程(2)。记 d = (a, m)，以及 t = dq  r，qZ，r = 0, 1, 2, , d  1， 则 x = x 0  qm rdmxrdm0(mod m)，0  r  d  1。 容易验证，当 r = 0, 1, 2, , d  1 时，相应的解 dmdxdmxdmxx)1(20000，，，， 对于模 m 是两两不同余的，所以同余方程(2)恰有 d 个解。证毕。 在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。 例 1 设(a, m) = 1，又设存在整数 y ，使得 a...