文档介绍：第四章同余方程教学目的和要求(1)理解同余方程(组)的基本概念,(2)熟练掌握一次同余方程的解法,掌握质数模的同余方程解的定理及其联系。(3)熟练掌握奇质数p的平方剩余和平方非剩余的欧拉判别条件,会求模p的平方(非)剩余。(4)正确理解勒让德符号和雅可比符号的概念、区别和联系,会利用二次反转律等性质求平方(非)剩余。本章在讲授孙子定理的基础上,使学生理解孙子定理及其在解同余方程中的基础作用。第一节一次同余方程定义1设f(x)=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)的解,则模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)等价于不定方程ax-my=b,(3)因此,因此由第二章第一节定理1知(2)有解的充要条件是d|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个解。证毕。第一节同余方程的基本概念注:(1)定理1说明了:若(a,m)|b,则(2)式有(a,m)个解;若(a,m)†b,则(2)式无解。(2)在定理的证明中,同时给出了解同余方程(2)的方法,但是,对于具体的同余方程(2),常常可采用不同的方法去解。第一节同余方程的基本概念例1例1解下列同余方程:(1)8x≡9(mod11)(2)9x≡6(mod15)