初等数论第四章同余式

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

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

2、)等价；（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/8/215三、一次同余方程的基本解法定理2设a，b是整数，a0(modm)。则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d=(a,m)个解。特别地，若(a,m)＝1，则方程（2）有唯一解。证明axb(modm)同余方程(2)等价于不定方程axmy=b，(

3、3)因此，第一个结论可由第二章第一节定理1〔P25〕得出。2021/8/216若同余方程(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/8/217容易验证，当r=0,1,2,,d1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。解方程(2)的方法：先求出相应不定方程axmy=b的一个特解2021/8/218例1解同余式故原同余式有3个解。所以

4、原同余式的解为2021/8/219四、其他解法定理3axb(modm)证:直接验算，有axbymb(modm)。注：将一个对于较大模m的同余方程转化为一个对于较小模a的同余方程，设mr(moda)，r

5、8/2113四、其他解法——减小系数定理4设a>0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程等价于同余方程axb(modm)证：设x是axb(modm)的解，即x是同余方程的解。由假设条件知：这两个同余方程都有且只有一个解，所以这两个同余方程等价。2021/8/2114例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/8/2115定理5四、其他解法——应用欧拉定理设(a

6、,m)=1，并且有整数>0使得a1(modm)，则同余方程axb(modm)的解是xba1(modm).注1：直接验证即可。注2：由定理5及Euler定理可知，若(a,m)=1，则xba(m)1(modm)是同余方程axb(modm)的解。例4解同余方程解：xba(21)12021/8/2116五、简单同余方程组〔模相同〕的解法例5解同余方程组解:将(*)的前一式乘以2，后一式乘以3，相减得到(*)19y4(mod7)，即5y4(mod7)，y2(mod7)。再代入(*)的前一式得到3x101(mod7)，x4(mod7)。即同余方程

7、组(*)的解是x4，y2(mod7)。注：同余方程组的解法与方程组的解法相似。2021/8/2117§4.2孙子定理2021/8/2118问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕分析：设所求物数为x，则有称之为同余式组。即要求这些同余式的公共解。2021/8/2119问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕为什么啊？除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×723