■ 一勒让德符号定义
■二欧拉判别法则 ■三高斯引理 ■四定理3及其证明
2013-4 10
一勒让彳惠符号定以
思考题（一）：.O o （r ） 求模17的平方剩余和平方非剩余
第
章
二次同余式与平方剩余
4. 3勒让彳惠苻号
ate
勒iJL 徳号定义
思考题(二)：・。

辽］
判断5是不是模17的平方剩余？
52 = 25 = 8(mod 17) , 51 =82三—l(mod 17) 5s = (-4) =16 = -1 (mod 17)
所以5是模17的平方非剩余
2013-4 10ate
1717丿
9)
17>
侧朗;卅)需)需)
1
-1
—r勒庁上德符号
定义1设p是素数，定义勒让德符号如下: 卜若。

是模"的平方剩余
(a)= < -L若d是模#的平方非剩余
P 0,若 p'a
2013-4 10 ate
Sodp)有解或杖有解.
2013-4 10
定土甲.1(欧扌立判 另IJ 法贝IJ) 设 P 是奇-素数，贝驭寸
任意執数a,
(自三a 乎(mod p)
例2证明2是模17平方剩余；3是17 平方非剩余. 解:因为(17-1 )/2=2',且有
2 = 4,2’ = 4 = —1,2、= (— I)2
= l(mod 1 7)
由定义駅
政协同余式*劭
敦论
~r
勒德符号
瓠P 冋财■仔卜1,翻»
二欧拉判别法
根据欧拉判断法则，并注意到a 二1
时, = 1以及a=・l 时，<<=（一1）丁，且P 是 奇数.
推论1,设p 是奇素数，则
例1若质数9=如+1,期一1是p 的平方剩余；若P0
4匕一I..则一1是P 的平方非剩余.
(D
(2) — =(—1尸
I P 丿
二欧拉判别法
2013-4-10 敷陀 7
二欧拉判另！J 法
证由推论知，当卩二4叶1时, =1；而当pB“一l时『
=一1・于是由定义知绪论成立.
二欧拉判别法
推论2设p是奇索数，刃R么
若p 三 1 (mod 4) 若p 三
3(mod 4) iiR木2掬；区久J立旳J另U法贝iJ • 找彳门YZ
=(一1)丁
贝IJWX L K轄数k仗码卩=41<+1,从而 (于〕=j 2013-4 10
二欧拉判别法
(iii)设 3"则(p)
=1
2013-4-10 Ste
1 ( mod 4)
=(_1 尸
ab
、
/
、
a
、P<pj I P J 若p三3(mod 4),则存在IE整数k使得
P=4k + 3.从而
定理2设p是奇索数，则
(H)
2013-4 10
二欧拉判别法
因为勒让徳符号取值±1,且p 是奇素 数，所以我们有
'ab 、
I P ?
<p
I P
二欧拉判别法
ill: (i) I 大I 为
= a 4- p(mod p)
咎价 JT4:^工弋
x 2 = a(mod p)
所以
(ii) 根抑;欧扌立判别法则，我彳门有 厂a 、
I P J
J
( b 、
BZ1
(mod p),
= b 2 (mod p)
ab
P-1
三(ab) ' (mod p)
2013-4 10
(ab)
p-1 p-l p-1
(b)
=(ab) r =a T b T
=
<P>
<p<pj
(mod p)
2013-4 10
推论设p 是奇素数，如果整数爲b 满足
2013-4 10
证：由欧拉判别法则及a = b(mod p) 知 —=a 2 = b 2
= — (mod p) I P 丿 I P 丿
所以 一 ——=0(mod p) I P 丿I P 丿 证毕.
2013-4-10
敷堆
冇
—
◎
<p>
\P \P
证毕.
a = b(mod p),则
（
(b
、
a
I P
二欧拉判别法
(iii)设(“，p)=l,所以 p/a,则根据(ii)
1二欧拉判别法
2013-4 10
三高斯弓I理
)!= I I ak = n a f i b
k —・K 1 j—1 J
(—l),n I I tij fl (p —b )(mod p)
易矢口 , …，p —・・・，p —叽是
模P网网不同余的，否则，我们有ak = p —
ak」,S^ak + ak」三0(mod p)
三高斯弓I理
因而匕+kj三0(mod p), 这不可自巨，因为 1 M k + k V + 已二v p.
1 J
2 2” 因为(a k , p) = I ,k = 1, • • •, P 以
个整数码,…,a., p _ — b m
是1,…，呼的一个排列，故
2
2013-4 10ate
2013-4 10
三高斯弓I理
a叮(&^)!三(-1) fla.nCp-b )
(:]=(-l)m证毕.
2013-4 10
例子計算勧镶徳拧兮(書)的値。

这电寺S-丄)=\ (31-1 )-15.我們求
出，數口
15, —30, 3-15^45, 4・ 15=60, 5-15=75,
G・1 7・ 15^105, 8・ 15=120・9-W—135.
10.15—15(), 11 ・ 15 = 165・工2・ 1活=180. 1B-I5=1<>f
1.4-15 = 210, 15.15—226
钺31除时所得的余数分別处：
15130,14,^»18,28,12,27,11,2«,10,25>9,24,8.
我們石山，共有7个余数：
30,29,28,27,26,25,24,
是大丁寺护==弩旳。

所以，(醫)=(—H )7" —*1.
2013-4-10 2»=（一1广津］1）!（口“
P-I
£1丁三(—1 )n, ( mod
再根拥定上里1及P是奇素数, 得至I」我们
2013-4 10
三高斯弓I 理
定理3设p 是奇素数.
(i) — =(一 1) I P 丿
(ii)若(a,2p) = l,则
(、
a
=(一
ak
JP
丿
L P
J
2013-4-10
ate
21
P T
8
9
定理3的证明
uE 因为
+ !；,() v r k V p,k = 1,
p-1
对k = i,•…，与1
求和，我们有
p 2
-1 宁「ak a — = PS 8 —
p-l
P -I
=PS
+ ± 込 +±(p-b ) + 2±b - mp •-1 J
J -> 一
P 一
+牙“p + 2討
ate
2013-4 10
定理3
的证明
内此,
2 _ |
因而mm --------- (mod 2)
8
p-
z
八 P~ 一 i 丁 ak
十 m(mod 2)
若a = 2,贝i 」OS
ak
若a 为奇数,
则m 三* k=1
ak
一(mod 2)
2013-4 10
定理3白勺证明。