初等数论四夏子厚.pptVIP

初等数论(四) 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)，常常可采用不同的方法去解。 第一节 同余方程的基本概念 例1 例1 解下列同余方程： （1）8x≡9（mod 11） （2）9x ≡ 6（mod 15） 第一节 同余方程的基本概念 解：（1）由（8，11）=1，知同余方程有唯一解。 原式同解于8x≡9+11（mod 11） 即2x ≡ 5 ≡ 5+11（mod 11） 所以x ≡ 8（mod 11）。 这个过程可简化:x≡ ≡ ≡ ≡ ≡ 8（mod 11） 所以x ≡－3 ≡8（mod 11） 第一节 同余方程的基本概念 （2）由（9，15）=3，3∣6，知同余方程有三个解。 先解3x ≡ 2（mod 5） 即3x ≡ 2+10（mod 5） 所以x ≡ 4（mod 5） 故由定理1知，原同余方程的解为 x ≡ 4，4+5×1，4+5×2（mod 15） 即x ≡ 4，9，14（mod 15）。 第一节 同余方程的基本概念 注：这种解法是同解变形法，是利用同余性质，将同余方程（2）通过适当的变形而求得其解的常用方法。本解法经常用到“倍乘变形”，应注意所乘倍数必须与同余方程的模数互质，否则不能保证同解。 第一节 同余方程的基本概念 例2 解同余方程：111