p1
( x2 a)xq( x) (a 2 1)x
若a是模p的二次剩余，
p1
p1
则0 x(x p1 1) x p x (a 2 1)x(mod p) a 2 1(mod p).
p1
反之，若a 2 1(mod p)，则( x2 a)xq( x) x p x 0(mod p)
p1
a 2 1(mod p) (3)
2019/9/15
13
例如：x2 a(mod11)
取模11的一个简化系为1, 2, 3,4, 5.
111
111
可以验证：1 2 1(mod11); (2) 2 1(mod11);
111
111
111
3 2 1(mod11); 4 2 1(mod11);5 2 1(mod11).
所以据§4.4-TH5[P86]知，平方剩余的个数等于p
2
1
.
又模p的简化系中含有p-1个元素，
从而平方非剩余的个数等于 p 1 .
2
显然数列12 , 22 , ,( p 1)2中含有 p 1 个数，
2
2
易证其两两对p不同余.
p1
且满足(n2 ) 2 n p1 1(mod p). 得证.
2019/9/15
5
三、同余式 y2 A 0(mod p ) 解的讨论
1、当 p A时，有解，且其解易求。
例1. y2 81 0(mod 33 ) y2 0(mod 33 ) y 0(mod 32 ) y 0,9，18(mod 33 )
2、当p ŒA时，可化为y2 A 0(mod p ),( A, p ) 1.
模7的平方剩余为1，2，-3； 平方非剩余为 -1，-2，3. 且有：1 12(mod7);2 32(mod7);3 22(mod7).
2019/9/15
19
定理2的证明：
由定理1知，平方剩余的个数等于同余式
p1
p1
x 2 1(mod p) 的解数，由 x 2 1 x p x，
0， p n；
(
n p
)

1， n是p的平方剩余； 1，n是p的平方非剩余.
如, 1与4是模5的平方剩余，2与3是模5的平方非剩余，
所以有
(1) 1， ( 2) 1， ( 3) 1， (4) 1，(5) 0.
5
5
5
5
5
2019/9/15
22
二、基本性质
n
p1
(1) ( ) n 2 (mod p);
解：x2 x 1 0(mod72 ) 4( x2 x 1) 0(mod72 )
即(2x 1)2 3 0(mod72 ) 令y 2x 1,
y2 3 0(mod72 )

(2)
而y2 3 0(mod7)的解为y 2(mod7).
令y 7t 2,代入(2)， 4t 1 0(mod7).
令x 5t 1, 代入原方程得(5t 1)2 1 0(mod52 ) 即10t 0(mod52 ) t 0(mod5) t 5s x 25s 1, 即原方程的解为x 1(mod52 ).
2019/9/15
7
例3. 解同余式 x2 x 1 0(mod72 ) (1)
若 x2 a(modm有) 解，则a称为模m的平方剩余； 否则，称a为模m的平方非剩余。
例4.求m 3,5,7,11的平方剩余和平方非剩余.
解：要使x2 a(mod 3)有解，且(a,3) 1. 只要求出x 2对模3的余数即可.
12 1(mod 3),22 1(mod 3), ∴ 模3的平方剩余为1；平方非剩余为2(或-1).
2019/9/15
17
x2 a(mod p), (a, p) 1, p为单质数 (1)
a是模p的二次非剩余的充要条件是
p1
a 2 1(mod p) (3)
证明：由(a, p) = 1
p1
p1
a p1 1 （a 2 1（) a 2 1) 0(mod p)
由（1） a是模p的二次剩余的充要条件是
2019/9/15
4
ax2 bx c 0(mod p ), p Œ(a,b,c) (2) 4、当p 2, 2 寣a,2 b时，(2)有解 2 c
f '( x) 2ax b 0(mod 2)无解 由§4.3－TH2〔P82〕知
(2)有解 ax2 bx c 0(mod 2) 2 c
2019/9/15
20
§5.3 勒让德符号
利用欧拉判别条件虽然可以判定 x2 a (mod p) 的解的存在性，但对较大的质数模，实际运用很困难。 通过引入勒让德符号，本节给出了较方便的判别方法。
2019/9/15
21
一、Legendre符号
定义 给定奇素数p，对于整数n，定义Legendre符号为
p
(2)
(
1
)

1,
(
1)

(1)
p1
2;
p
p
(3)
a

a1(mod
p)

(
a) p

(
a1 p
);
(4) ( a1a2 an ) ( a1 )( a2 ) ( an );
p
pp p
(5) ( ab2 ) ( a ), p 宐b. pp
2019/9/15
2019/9/15
9
例4.求m 3,5,7,11的平方剩余和平方非剩余.
x(m 3)
1
2
x2的余数(m 3) 1
1
x(m 5)
1 2
x2的余数(m 5) 1
4
∴ 模5的平方剩余为±1；平方非剩余为±2.
2019/9/15
10
x(m 7)
1 2
3
x2的余数(m 7) 1
111
111
而 (1) 2 1(mod11); 2 2 1(mod11);
111
111
(3) 2 1(mod11); (4) 2 1(mod11);
111
(5) 2 1(mod11).
∴ 模11的平方剩余为1，-2，3，4，5；
平方非剩余为-1，2，-3，-4，-5.
3
2
∴ 模7的平方剩余为1，2，-3； 平方非剩余为 -1，-2，3.
x(m 11)
12 3 4 5
x2的余数(m 11) 1 4 2 5 3
∴ 模11的平方剩余为1，-2，3，4，5；
平方非剩余为-1，2，-3，-4，-5.
2019/9/15
11
§5.2单质数的平方剩余与平方非剩余
本节讨论形如 x2 a(mod p), (a, p) 1, p为单质数 (1)
2019/9/15
3
ax2 bx c 0(mod p ), p Œ(a,b,c) (2) 3、当p 2, p Œa时， y2 A 0(mod p )
由于( p ,4a) 1， ax2 bx c 0(mod p ) 4a(ax2 bx c) 0(mod p ) (2ax b)2 A 0(mod p ), A b2 4ac 代换即得 y2 A 0(mod p )
x2 a(mod p)
2019/9/15
16
x2 a(mod p), (a, p) 1, p为单质数 (1)
若a是模p的二次剩余，则方程(1)有两个解；
p1
证明：由x p x ( x2 a)xq( x) (a 2 1)x,
p1
且 a 2 1 0(mod p)
2019/9/15
14
例如：x2 a(mod11) 模11的平方剩余为1，-2，3，4，5.
方程 x2 1(mod11)的解为：x 1,10(mod11); 方程 x2 2(mod11)的解为：x 3,8(mod11); 方程 x2 3(mod11)的解为：x 5,6(mod11); 方程 x2 4(mod11)的解为：x 2,9(mod11); 方程 x2 5(mod11)的解为：x 4,7(mod11).
1、当p a , p b, p 宑c时，无解.
2、当 p a , p 宑b时，一定有解.. . f '( x) 2ax b 0(mod p)无解, 由§4.3－TH2〔P82〕知
(2)有解 ax2 bx c 0 (modp)有解 bx c 0 (modp)有解 (b, p) 1
一般地，对同余式(2)的求解，最终可以转化为同余式 x2 a(mod p ), p是素数
或者，x2 a(modm)，(a,m) 1.
2019/9/15
6
例2. 解同余式 x2 3 0(mod52 )
解:同余式 x2 1 0(mod5)的解为 x 1(mod5),
2019/9/15
15
x2 a(mod p), (a, p) 1, p为单质数 (1)
p1
a是模p的二次剩余的充要条件是 a 2 1(mod p) (2)
p1
证明：由 x2 a x p1 a 2 q( x)，使得
p1
p1
p1
x p1 a 2 ( x2 a)q( x) x p x x( x p1 a 2 ) (a 2 1)x
的同余式的解。