初等数论四-夏子厚

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

1、初等数论(四)NumberTheory（Chap4）信阳职业技术学院夏子厚第四章同余方程教学目的和要求（1）理解同余方程（组）的基本概念，（2）熟练掌握一次同余方程的解法，掌握质数模的同余方程解的定理及其联系。（3）熟练掌握奇质数p的平方剩余和平方非剩余的欧拉判别条件，会求模p的平方（非）剩余。（4）正确理解勒让德符号和雅可比符号的概念、区别和联系，会利用二次反转律等性质求平方（非）剩余。本章在讲授孙子定理的基础上，使学生理解孙子定理及其在解同余方程中的基础作用。第一节一次同余方程定义1设f(x)=

2、anxna1xa0是整系数多项式，称f(x)0(modm)(1)是关于未知数x的模m的同余方程，简称为模m的同余方程。若an0(modm)，则称（1）式为n次同余方程。第一节同余方程的基本概念定义2若整数x0满足f(x)0(modm),则xx0(modm)称为(1)的解。凡对于模m同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。因此同余方程(1)的解数不超过m。第一节同余方程的基本概念注：1、若x0是(1)的

3、解,则模m的剩余类Kx0,即全部整数x0+km,k=0,±1,±2,…中每一个数都是满足(1),而x0是Kx0中的非负最小整数,即是非负最小剩余。2、由定义可知,要求(1)的解,只要逐个把0,1,2,…,m-1或把模m的绝对最小剩余系代入(1)中进行验算即可。但当m大时,计算量往往太大。第一节同余方程的基本概念定理1设a，b是整数，d=(a,m)a0(modm)。则同余方程axb(modm)(2)有解的充要条件是db。若(2)有解，则恰有d个解。第一节同余方程的基本概念证明显然，同余方程(2)等

4、价于不定方程ax－my=b，(3)因此，因此由第二章第一节定理1知(2)有解的充要条件是d

5、b。第一节同余方程的基本概念若同余方程(2)有解x0，则存在y0，使得x0，y0是(3)式的解，此时，(3)式的全部解是，tZ。(4)由式(4)所确定的x都满足式(2)。第一节同余方程的基本概念记t=dqr，qZ，r=0,1,2,,d1，则x=x0qm(modm)。易证，当r=0,1,2,,d1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。第一节同余方程的基本概念注

6、：（1）定理1说明了：若（a,m）

7、b,则（2）式有（a,m）个解；若（a,m）†b,则（2）式无解。（2）在定理的证明中，同时给出了解同余方程(2)的方法，但是，对于具体的同余方程(2)，常常可采用不同的方法去解。第一节同余方程的基本概念例1例1解下列同余方程：（1）8x≡9（mod11）（2）9x≡6（mod15）第一节同余方程的基本概念解：（1）由（8，11）=1，知同余方程有唯一解。原式同解于8x≡9+11（mod11）即2x≡5≡5+11（mod11）所以x≡8（mod11）。这个过程可简

8、化:x≡≡≡≡≡8（mod11）所以x≡－3≡8（mod11）第一节同余方程的基本概念（2）由（9，15）=3，3∣6，知同余方程有三个解。先解3x≡2（mod5）即3x≡2+10（mod5）所以x≡4（mod5）故由定理1知，原同余方程的解为x≡4，4+5×1，4+5×2（mod15）即x≡4，9，14（mod15）。第一节同余方程的基本概念注：这种解法是同解变形法，是利用同余性质，将同余方程（2）通过适当的变形而求得其解的常用方法。本解法经常用到“倍乘变形”，应注意所乘倍数必须与同余方程的模数互

9、质，否则不能保证同解。第一节同余方程的基本概念例2解同余方程：111x≡75（mod321）解由（111，321）=3，3ㄧ75，知同余方程有三解。先解同余方程37x≡25（mod107）其对应的不定方程为37x+107y=25其特解：x=－8,y=3。于是x≡－8≡99（mod107）因此，原同余方程的三个解为：x≡99，99＋107，99＋107×2（mod321）即x≡99，206，315（mod321）第一节同余方程的基本概念注：前面介绍的同解变形法，对于模数较小的同余方程，使用起来比较方便

10、，但对模数较大的同余方程就难于奏效。这时可以考虑转化为不定方程求解。第一节同余方程的基本概念例3设(a,m)=1,m>0,则axb(modm)恰有一解,且xba(m)-1(modm)证明：由定理1及Euler定理即得：xba(m)-1(modm)是axb(modm)的唯一解。第一节同余方程的基本概念例4解下列同余方程：7x1（mod31）解：由（7,31）=1，知同余方程有唯一解.又31是质数，因而(31)=30于是（mod31）因此，同余方程的解为x