初等数论§4同余式

《初等数论§4同余式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章同余式§4.1基本概念及一次同余式2021/9/181阜阳师范学院数科院一、基本概念是关于模m的同余方程，或同余式。则称为n次同余方程。则剩余类里的元素都满足该方程。定义12021/9/182阜阳师范学院数科院定义2设a是整数，当成立时，则称是同余方程(1)的一个解。即与a同余的一切整数作为（1）式的一个解。注：同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。显然，同余方程(1)的解数不超过m。2021/9/183阜阳师范学院数科院二、等价同余式定理1下面的结论成立：（1）设b(

2、x)是整系数多项式，则同余方程(1)与f(x)b(x)b(x)(modm)等价；（2）设b是整数，(b,m)=1，则同余方程(1)与bf(x)0(modm)等价；（3）设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)0(modm)或h(x)0(modm)的解。2021/9/184阜阳师范学院数科院三、一次同余方程的基本解法定理2设a，b是整数，a0(modm)。则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d

3、=(a,m)个解。特别地，若(a,m)＝1，则方程（2）有唯一解。证明axb(modm)同余方程(2)等价于不定方程axmy=b，(3)因此，第一个结论可由第二章第一节定理1〔P25〕得出。2021/9/185阜阳师范学院数科院若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，由式(4)所确定的x都满足方程(2)。axb(modm)(2)axmy=b(3)此时，方程(3)的解是记d=(a,m)，以及t=dqr，qZ，r=0,1,2,,d1.0rd1。2021/9/186阜阳师范学院数科院容易验证

4、，当r=0,1,2,,d1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。解方程(2)的方法：先求出相应不定方程axmy=b的一个特解2021/9/187阜阳师范学院数科院例1解同余式故原同余式有3个解。所以原同余式的解为2021/9/188阜阳师范学院数科院四、其他解法定理3axb(modm)证:直接验算，有axbymb(modm)。注：将一个对于较大模m的同余方程转化为一个对于较小模a的同余方程，设mr(moda)，r

5、阜阳师范学院数科院例2解同余方程325x20(mod161)解d=1,原同余方程即是3x20(mod161)。解同余方程161y20(mod3)，2y1(mod3)，得到y2(mod3)，因此原方程的解是2021/9/1810阜阳师范学院数科院补充说明2021/9/1811阜阳师范学院数科院例1解同余式另解：先解同余方程2021/9/1812阜阳师范学院数科院四、其他解法——减小系数定理4设a>0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程等价于同余方程axb(modm)证：设x是axb(modm)的解，

6、即x是同余方程的解。由假设条件知：这两个同余方程都有且只有一个解，所以这两个同余方程等价。2021/9/1813阜阳师范学院数科院例3解同余方程6x7(mod23)。解由定理4，依次得到6x7(mod23)5x732(mod23)3x248(mod23)2x8×710(mod23)x5(mod23)。axb(modm)2021/9/1814阜阳师范学院数科院定理5四、其他解法——应用欧拉定理设(a,m)=1，并且有整数>0使得a1(modm)，则同余方程axb(modm)的解是xba

7、1(modm).注1：直接验证即可。注2：由定理5及Euler定理可知，若(a,m)=1，则xba(m)1(modm)是同余方程axb(modm)的解。例4解同余方程解：xba(21)12021/9/1815阜阳师范学院数科院五、简单同余方程组〔模相同〕的解法例5解同余方程组解:将(*)的前一式乘以2，后一式乘以3，相减得到(*)19y4(mod7)，即5y4(mod7)，y2(mod7)。再代入(*)的前一式得到3x101(mod7)，x4(mod7)。即同余方程组(*)的解是x4，y2(mod7)。

8、注：同余方程组的解法与方程组的解法相似。2021/9/1816阜阳师范学院数科院§4.2孙子定理2021/9/1817阜阳师范学院数科院问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几