高次同余式的解数及解法

《高次同余式的解数及解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4.3高次同余式的解数及解法本节初步讨论高次同余式的解数与解法：先把合数模的同余式化成质数模的同余式，然后通过下一节来解质数模的同余式。A回顾与强调二、同余式解的相关定理上一节由孙子定理：设m1,m2,L,mk是正整数，(mi,mj)=1，m=m1m2Lmk，Mi=，MiMi＇≡1(modmi)，同余式组（同余方程组）(1)的解为(modm)。反过来，解同余式，可将它化为同余式组，于是，有下面的定理B重要定理证明的讲解定理1设m=m1m2Lmk，其中m1,m2,L,mk是两两互素的正整数，f(x)是整系数多项式，则A：同余式f(x)≡

2、0(modm)（1）与同余式组f(x)≡0(modmi)（1≤i≤k）（2）等价；B：以T与Ti（1≤i≤k）分别表示f(x)≡0(modm)与f(x)≡0(modmi)（1≤i≤k）的解的个数，则T=T1T2…Tk。证明A：设x0是适合（1）的解，即f(x0)≡0(modm)，由整除的性质知f(x0)≡0(modmi)，1≤i≤k，反之，设x0是适合（2）的解，即f(x0)≡0(modmi)，1≤i≤k，则m1,m2,L,mk是两两互素的正整数知，f(x0)≡0(modm)，故（1）与（2）同解。B：设同余方程(2)的全部解是(mo

3、dmi)，（3）即模mi有Ti个解，则同余方程组(2)等价于下面的T1T2…Tk个方程组：（4）其中通过式(3)中的数值，即通过同余方程(1)的全部解。由孙子定理，对于选定的每一组{}，同余方程组(4)对模m有唯一解，而当每个通过(3)式中的值时，由孙子定理的证明知所得到的T1T2…Tk个同余方程组(4)的解对于模m都是两两不同余的。证毕。由定理4及算术基本定理，设，从而，解一般模的同余方程可以转化为解模为素数幂的同余方程组。下面我们利用数学中的化归思想对模pα的同余方程做进一步讨论容易看出，若x0是同余方程f(x)≡0(modpα)

4、(5)的解，则它必是方程f(x)≡0(modpα-1)(6)的解，因此，必有与x0相应的方程(6)的某个解x1，使x0≡x1(modpα-1)，x0=x1+pα-1t0，t0∈Z。这提示我们：可以从方程(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(modp)，则存在整数t

5、，使得x=x1+pα-1t(7)是同余方程(5)的解。(ⅱ)若f＇(x1)≡0(modp)，并且f(x1)≡0(modpα)，则对于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(modpα)(8)利用泰勒展开式将f(x1+pα-1t)在x1处展开得f(x1)+pα-1tf＇(x1)≡0(modpα)，由于x1是

6、f(x)≡0(modpα-1)的解(pα-1

7、f(x1)),上式两端同除pα-1tf＇(x1)≡-(modp)(9)下面考虑两种情形。(ⅰ)若f＇(x)≡0(modp)，则关于t的同余方程(9)有唯一解t≡t0(modp)，即t=t0+pk（k∈Z）代入x=x1+pα-1t得x≡x1+pα-1t0(modpα)是同余方程(5)的解。(ⅱ)若f＇(x1)≡0(modp)，并且f(x1)≡0(modpα)，则式(5)对于任意的整数t成立，即同余方程(5)有p个解t≡i(modp)，0≤i≤p-1。于是x≡x1+pα-1i(modpα)，0

8、≤i≤p-1，都是同余方程(5)的解。证毕。在定理中，没有对f＇(x1)≡0(modp)并且f(x1)≡0(modpα)的情形进行讨论。事实上，此时，同余方程(6)无解。即，我们无法从同余方程(6)的解x1出发去求得同余方程(5)的解。由定理，可以把解同余方程(5)，转化为解同余方程f(x)≡0(modp)(10)事实上，由方程(10)的解，利用定理，可以求出方程f(x)≡0(modp2)的解，再利用定理，又可以求出方程f(x)≡0(modp3)的解，LL，直到求出方程(5)的解。C总结本节主要讲解了解把高次同余式划归为模pα的同余式

9、，进一步划归为求模p的同余式（质数模的同余式）-化归思想。D讲解例题三、高次同余式解法举例例1解同余方程2x2+13x-34≡0(mod53)。解容易验证，同余方程2x2+13x-34≡0(mod5)有两个解x≡-1，2