资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
本文格式为Word版,下载可任意编辑高次同余式的解数及解法 4.3高次同余式的解数及解法 本节初步议论高次同余式的解数与解法:先把合数模的同余式化成质数模的同余式,然后通过下一节来解质数模的同余式。 A回想与强调 二、同余式解的相关定理 上一节由孙子定理:设m1, m2, L, mk是正整数, (mi, mj) = 1,m = m1m2Lmk ,Mi = , MiMi 1 (mod mi),同余式组(同余方程组)(1) 的解为 (mod m)。反过来,解同余式 ,可将它化为同余式组 ,于是,有下面的定理 B重要定理证明的讲解 定理1设m = m1m2Lmk ,其中m1, m2, L, mk 是两两互素的正整数,f(x)是整系数多项式,那么 A:同余式 f(x) 0 (mod m) (1) 与同余式组f(x) 0 (mod mi) (1 i k) (2) 等价; B:以T与T(分别表示f(x) 0 (mod m)与f(x) 0 i1 i k)(mod mi) (1 i k)的解的个数,那么T = T1T2Tk 。 证明 A:设x0是适合(1)的解,即f(x0) 0 (mod m),由整除的性质知 f(x0) 0 (mod mi) ,1 i k, 反之,设x0是适合(2)的解,即f(x0) 0 (mod mi) ,1 i k,那么m1, m2, L, mk是两两互素的正整数知,f(x0) 0 (mod m),故(1) 与(2)同解。 B:设同余方程(2)的全部解是 (mod mi), (3) 即模mi有Ti个解,那么同余方程组(2)等价于下面的T1T2Tk个方程组:(4) 其中 通过式(3)中的数值,即通过同余方程(1)的全部解。 由孙子定理,对于选定的每一组 ,同余方程组(4)对模m有唯一解,而当每个 通过(3)式中的值时,由孙子定理的证明知所得到的T1T2Tk个同余方程组(4)的解对于模m都是两两不同余的。证毕。 由定理4及算术根本定理,设 , 从而,解一般模的同余方程 可以转化为解模为素数幂 的同余方程组 。 下面我们利用数学中的化归思想对模p的同余方程做进一步议论轻易看出,若x0是同余方程 f(x) 0 (mod p) (5) 的解,那么它必是方程 f(x) 0 (mod p-1) (6) 的解,因此,必有与x0相应的方程(6)的某个解x1,使 x0 x1 (mod p-1),x0 = x1 + p-1t0,t0Z。 这提示我们:可以从方程(6)的解中去求方程(5)的解。于是,现在的问题是,对于方程(6)的每个解x1,是否必有方程(5)的解x0与之对应?若有,如何去确定它? 定理2 设p是素数,a 2是整数,f(x) = anxn + L + a1x + a0是整系 数多项式,又设x1是同余方程(6)的一个解。以f(x)表示f(x)的导函数。 () 若f(x1) 0 (mod p),那么存在整数t,使得 x = x1 + p-1t (7) 是同余方程(5)的解。 () 若f(x1) 0 (mod p),并且f(x1) 0 (mod p),那么对于t = 0,1, 2, L, p - 1,式(7)中的x都是方程(5)的解。 证明 我们来说明,如何确定式(7)中的t,使x1 + p-1t得志同余方程(5),即要使 f(x1+ p-1t) =an(x1+ p- 1t)n+an-1(x1+ p-1t)n-1+L+a1(x1+ p-1t)+a0 0 (mod p) (8) 利用泰勒开展式将f(x1+ p-1t)在x1处开展得 f(x1) + p-1t f(x1) 0 (mod p), 由于x1 是f(x) 0 (mod p-1)的解(p-1 |f(x1) ),上式两端同除 p-1t f(x1) - (mod p) (9) 下面考虑两种情形。 () 若f(x) 0 (mod p),那么关于t的同余方程(9)有唯一解t t0 (mod p),即t = t0 + pk(kZ)代入x = x1 + p-1t得 x x1 + p-1t0 (mod p) 是同余方程(5)的解。 () 若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,都是同余方程(5)的解。证毕。 在定理中,没有对f(x1) 0 (mod p)并且 f(x1) 0 (mod p)的情形举行议论。事实上,此时,同余方程(6)无解。即,我们无法从同余方程(6)的解x1启程去求得同余方程(5)的解。 由定理,可以把解同余方程(5),转化为解同余方程 f(x) 0 (mod p) (10) 事实上,由方程(10)的解,利用定理,可以求出方程f(x) 0 (mod p2)的解,再利用定理,又可以求出方程f(x) 0 (mod p3)的解,LL,直到求出方程(5)的解。 C总结 本节主要讲解了解把高次同余式划归为模p的同余式,进一步划归为求模p的同余式(质数模的同余式)-化归思想。 D讲解例题 三、高次同余式解法举例 例1 解同余方程2x2 + 13x - 34 0 (mod 53)。 解 轻易验证,同余方程 2x2 + 13x - 34 0 (mod 5) 有两个解x -1,2 (mod 5)。 (i)令x = -1 + 5t,代入同余方程 2x2 + 13 x - 34 0 (mod 52), 得到 2(-1 + 5t)2 + 13(-1 + 5t) - 34 0 (mod 52), -45 + 45t 0 (mod 52), 9t 9 (mod 5),t 1 (mod 5),t = 1+ 5 t1。 于是,将t = 1+ 5 t1代入x = -1 + 5t得到 x = -1 + 5(1 + 5t1) = 4 + 25t1,t1Z。 将上式的x代入原同余方程得到 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)。 得到原同余方程的一个解 x = 4 + 25t1 = 4 + 25(2 + 5t2) 54 (mod 53)。 () 从同余方程的另一个解 x 2 (mod 5)启程利用上述方法,可以求出同余方程的另一个解。解略。 例2 解同余方程 x2 1 (mod 2k),kN。 (11) 解 若k = 1,那么方程(11)的解是x 1 (mod 2)。 若k = 2,那么方程(11)的解是x 1,-1 (mod 4)。 若k 3,那么同余方程(11)可化为 x2 - 1 = (x + 1)(x - 1) 0 (mod 2k), 的解必是奇数,设x = 2y + 1,那么同余方程(11)成为 6
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号