精品-优秀PPT课件--初等数论四-夏子厚.ppt

文档介绍：初等数论(四) Number Theory(Chap4)
信阳职业技术学院夏子厚
第四章同余方程
教学目的和要求
(1)理解同余方程(组)的基本概念,
(2)熟练掌握一次同余方程的解法,掌握质数模的同余方程解的定理及其联系。
(3)熟练掌握奇质数p的平方剩余和平方非剩余的欧拉判别条件,会求模p的平方(非)剩余。
(4)正确理解勒让德符号和雅可比符号的概念、区别和联系,会利用二次反转律等性质求平方(非)剩余。
本章在讲授孙子定理的基础上,使学生理解孙子定理及其在解同余方程中的基础作用。
第一节一次同余方程
定义1 设f(x) = anxn  a1x  a0是整系数多项式,称
f(x)  0 (mod m) (1)
是关于未知数x的模m的同余方程,简称为模m的同余方程。
若an 0 (mod m),则称(1)式为n次同余方程。
第一节同余方程的基本概念
定义2 若整数x0满足 f(x)0(mod m), 则 x x0 (mod m)称为(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)
a 0 (mod m)。则同余方程
ax  b (mod m) (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 (mod m)。
易证,当r = 0, 1, 2, , d  1时,相应的解
对于模m是两两不同余的,所以同余方程(2)恰有d个解。证毕。
第一节同余方程的基本概念
注:(1)定理1说明了:
若(a,m)|b, 则(2)式有(a,m)个解;
若(a,m)†b, 则(2)式无解。
(2)在定理的证明中,同时给出了解同余方程(2)的方法,但是,对于具体的同余方程(2),常常可采用不同的方法去解。