数论ch2-同余式(第4节).pptVIP

§4 同余式 定义4.1 设 f (x) ? anxn ? an?1xn?1 ? … ? a1x ? a0, 其中n 0, ai (i ? 0, 1,…, n)是整数. 又设m 0, 则 f (x) ? 0 (mod m) (1) 叫做模m 的同余式. 若 则 n 叫做同余式(1)的次数. 同余式的定义 如果 x0 满足 f (x0) ? 0 (mod m), 则 x ? x0 (mod m) 叫做同余式(1)的解. !! 同余式不同的解是指互不同余的解. 解同余式(验算法) 同余式 x5 ? 2x4 ? x3 ? 2x2 ? 2x ? 3 ? 0 (mod 7) 有3个解: x ? 1, 5, 6 (mod 7). 同余式 x4 ? 1 ? 0 (mod 16) 有8个解: x ? 1, 3, 5, 7, 9, 11, 13, 15 (mod 16). 同余式 x2 ? 3 ? 0 (mod 5) 没有解. 多元同余式 定义4.2 设m 0, k ? 2, F(x1,…, xk) 是一个k 元整系数多项式, 则称同余式 F(x1,…, xk) ? 0 (mod m) (2) 为模m 的k元同余式. 它的解为 x1 ? a1 (mod m), …, xk ? ak (mod m). 注:若至少有一个j使得aj bj (mod m), 则(a1,…, ak)和(b1,…, bk)被称为不同的解. 同余式解法举例 1.验证法 设p为素数, 记 Np 为同余式 y2 ? x3 ? 1 ? 0 (mod p)的解的个数. 则有: 1. N2 ? 2, 解为(x, y) ? (0, 1), (1, 0). 2. N3 ? 3, 解为(x, y) ? (1, 0), (2, 1), (2, 2). 3. N5 ? 5, 解为(x, y) ? (0, 2), (0, 3), (1, 0), (3, 1), (3, 4). 4. N7 ? 3, 解为(x, y) ? (1, 0), (2, 0), (4, 0). 一元一次同余式的解 定理4.1 设(a, m) ? 1, m 0, 则同余式 ax ? b (mod m) (3) 恰有一个解. 一元一次同余式的解 定理4.2 在定理4.1的条件下, x ? ba?(m)?1 (mod m) 是同余式(3)的唯一解. 举例 例1：解同余式 17x ? 19 (mod 25). 解: (1) x ? 19?17 20 ?1 ? 7 (mod 25). (2) 也可以利用Euclid算法计算 17?1 (mod 25), 再代入求解. 一元一次同余式解的个数 定理4.3 设m 0, (a, m) ? d, 则同余式 ax ? b (mod m) (4) 有解的充分必要条件是 d | b. 进一步, 若d | b, 则同余式 (4) 恰有d 个解. 举例 例2：解同余式28x ? 21 (mod 35). 解: 因为 (28, 35) = 7 | 21， 故原同余式有解, 且有7个解. 原同余式等价于4x ? 3(mod 5), 而它的解为 x ? 2(mod 5), 故原同余方程的解为 x ? 2, 7, 12, 17, 22, 27, 32(mod 35). 举例 例3：求下列联立同余式的解 x ? 4y ? 29 ? 0 (mod 143), 2x ? 9y ? 84 ? 0 (mod 143). 类似于方程的消元法求解. 消元时注意乘与模数互素的元素. 多元一次同余式解的个数 定理4.4 设k ? 1, 同余式 a1x1 ? a2x2 ? … ? ak xk ? b ? 0 (mod m) (5) 有解的充分必要条件是 (a1, a2, …, ak , m) | b. 若该条件满足, 则同余式(5)的解数为 mk?1(a1, a2, …, ak , m). * * 不同的解是指互不同余的解. * 同余式的解数可能超过同余式的次数. * “不同的解” * * 不同的解是指互不同余的解. * 同余式的解数可能超过同余式的次数. * “不同的解”