初 等 数 论 辅导课程十 主讲教师 曹洪平.

Presentation on theme: "初 等 数 论 辅导课程十 主讲教师 曹洪平."— Presentation transcript:

1 初 等 数 论 辅导课程十 主讲教师 曹洪平

2 勒让得符号 掌握勒让得符号的定义 熟练掌握勒让得符号的性质 能用勒让得符号的性质判别质数模 二次同余式是否有解

3 勒让得符号的定义 勒让得符号( )(读作a对p的勒让得符号) 是一个对于给定的单质数p定义在一切整 数a上的函数，它的值规定如下：

4 注 由勒让得符号的定义可以看出，如果 能够很快地计算出它的值，那么就会 立刻知道同余式 x2≡a（mod p） 有解与否，下面通过讨论勒让得符号 的性质给出计算勒让得符号的值的方 法。

5 勒让得符号的性质 性质1 （mod p）。 证由定义及欧拉判别法即得。

6 性质2 其中 （mod p） 证 由性质1可得前两式，由定义可得第 三式。

7 性质 。 证 由性质1， (mod p)。

8 由定义 又p>2，故得性质3。

9 性质 ，p∤b 。 性质5 ； 若（a，p）＝1，且2∤a，则 其中p1=(p-1)/2。

10 推论当p＝8m1时，2是模p的平 方剩余； 当 时，2是模p的平方非剩余。

11 性质6（二次反转定理）若p及q 都是单质数，（p，q）＝1，则 。

12 勒让得符号的应用 例判断同余式 （mod 563） 是否有解。

13 解因563为单质数，只须计算（ ）。 因为286＝2×11×13所以由性质3得 。 由性质5得

14 由性质6及性质2与性质4得 同理由前面性质得 故 ，因而原同余式无解。

15 合数模的情况 掌握同余式 (mod m), (a，m)＝1 (1) 有解的条件及解的个数。

16 若m的标准分解式为： 则（1）有解的充要条件是同余式组 x2 a (mod 2 ) x2a(mod ), i＝1，2，…，k （2） 有解，并且在有解的情况下，（1）的 解数是（2）中各式解数的乘积。

17 定理1x2a (mod p )， >0, (a, p)=1有
解的充要条件是 ，且在有解的 情况下，解数是2，这里p是单质数。

18 定理2设>1，则同余式 x2a(mod 2),  >1, (2, a)=1 有解的充要条件是 (i)当 ＝2时，a1(mod 4); (ii)当3时， a1(mod 8)。 并且在有解的情况下，若 ＝2，则 解数是2；若3 ，则解数是4。

19 定理3同余式x2a(mod m), , (a, m)=1 有解的必要条件是： 当=2时，a1(mod 4); 当3时，a1(mod 8)并且 i＝1，2，…，k。 若上述条件成立，则同余式有解，并且 当=0及1时，解数是2k，当=2时，解数 是2k+1，当3时，解数是2k+2。

20 例解x257(mod 64) 解因571(mod 8) ，故有四个解。将 x=±(1+4t3)代入x257(mod 16)得 (1+4t3)2 57(mod 16) 。由此得 t3 1(mod 2) ，故x= ±(5+8t4)是适合 x257(mod 16)的一切整数，又将这 一x代入同余式x257(mod 32) 可得 适合x257(mod 32)的一切整数为

21 x=±(5+16t5)。将此x代入x257(mod 64)
故原同余式的四个解为： x  21 ，53，－21，－53 （mod 64）。