第四章 (8) 高次同余式的解法、质数模的同余式

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

1、第四章高次同余式的解数及解法、质数模的同余式复习n定义若fx()表示多项式fx()ax++axa,n10其中am是整数;,又设是一正整数则ifx()0(modm)(1)叫做模m的同余式.若a0(modm),则n叫做(1)的n次数.由第三章§1定理2,若fa()0(modm),则剩余类K中任何整数a'都能使fa(')0(modm)成立.a定义若afa是使m()0(mod)成,立的一个整数则xam(mod)叫(1)做.的一解这就是说今后我们把适合(1)(1)式而对模m互相同余的一切数算作的一个解.同余式解的定义同余类cmmod中的任

2、一整数也是()1的解,这些解都应看作是相同的,把它们的全体算作是()1式的一个解,并把这个解记为xc(modm).这实际上是把同余类cmodm看作是满足(1)的一个解.当cc,均为同余式的解,且对模m不同余(即cmodmc,modm1212是不同的同余类)时才看成是()1的不同的解.我们把所有对模m两两不同余的()1的解的个数(即满足(1)的模m的同余类的个数)称为是()1的解数.因此我们只要在模m的一组完全剩余系中来解模m的同余式.显然,模m的同余式的解数至多为m.定理一次同余式axbma(modm),0(mod)(2)有解的充要条件是

3、(.amb,)

4、若(2)(2)有解(),则的解数对模m来说是d(,).am由定理的证明可以看出,适合(2)式的整数也就是适合不定方程axmy-(4)b的解答中x的值,故同余式(2)可以用解不定方程(4)的方法去解它.(i)取aa(mod),m-m/2

5、yb+ax.6同样理由,上述不定方程与同余方程()11同时有解或无解.(iii)若取ymoda是()6的解,则xmodm010是(),5即()2的解,这里x(myb)/a(7).0011反过来,若xmodm是()25即()的解,则ymoda001是()6的解,这里y(axb)/m(8).此外,若ymod01010ay,'moda是()6的两个不同解,则相应地确定101xmodmx,'modm也是()5即()2的两个不同解.00所以()65和()的解数相同.以上步骤的(i),(ii),(iii)表明:求模m的同余式(),2通过同余式(

6、)56转化为求解较小的模a的同余方程().1如果()62能立即解出,则由(7)就得到()的全部解;如果()6还不容易解出,则继续对它用步骤(i),(ii),化为一模更小的同余式.这样进行下去总能使问题归结为求解一模很小且能直接看出其是否有解的同余式.再依次利用式(7)返回上去即可求得()2的全部解.孙子定理定义设fx()jk是1整系数多项式(),把含有j变数x的一组同余式fx()m0(modjk),1,jj称为是同余式组.若整数c同时满足fc()m0(modjk),1,jj则称是同余式组(1)的解.同余式组解的定义同余类cmod

7、mm,[m,,m]中的任一整数也是同余式1kfx()0(modm)(1jk)的解,这些解都应看作是相同的,jj并把这个解记为xc(modm).这实际上是把同余类cmodm看作是满足同余式组的一个解.当cc,均为同余式组的解,且对模m不同余时才看成是同余12式组的不同的解.我们把所有对模m两两不同余的同余式组解的个数称为同余式组的解数.因此我们只要在模m的一组完全剩余系中来解同余式组,解数至多为m.此外,只要同余式组中任意一个同余式无解，则同余式组一定无解.大约公元56-世纪,我国南北朝时期有一部著名的算术著作《孙子算经》,其中有这样一

8、个“物不知数”问题：“今有物,不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这就是要求同余方程组x2(mod3)x3(mod5)的正整数解.书中求出了满足这一问题的最小x2(mod7)正整数解x23.因此把定理1称为孙子剩余定理或孙子定理国际上称为中国剩余定理.定理1(孙)子定理设m,,m是km个两m两互m质的正整数,,11kkmmMi,kx1,2,b,(mod,则m同余),式组iijj1jk(1)的解是'''xMMbMMbMMb(modm)(2)111222kkk'其中MMm1(mo

9、dik),1,2,,.iii证由(mm,)=1,ij即得(Mm,)1,故由§1定理即知ijii''对每一M,有一M存在,使得MM1(modm).