??1?? 1 如果 p?1(mod4). ?p???????1 如果 p?3(mod4) 证明 因为
(?1)由性质定理iii)得
(p?1)2? 1 如果 p?1(mod4). ???1 如果 p?3(mod4) ???1?(p?1)2(modp). ?p??(?1)??由于同余式两端都是?1，因此命题成立. ▋ 例1. 29 判断同余式x解 勒让德符号
2??38(mod13)是否有解？
，又因为38?12(mod13)，且
38??138?38??13??13??13???1312?3?22,于是
????再由
38?12??3?22??3?1313??13?13??.
3?3??13故同余式x2(13?1)2?36?272?1(mod13).
??38(mod13)有解.
另解：因为38??1(mod13)，所以
38??1??13??1338??138??1?1??1?1??13??13??13??13??13???13 ，因而有
2.
所以同余式x2??38(mod13)有解. ▋
p是奇素数,S是含有(p?1)定义1.17 设是模
2个整数的集合,如果S?(?S)?S???ss?S?p的一个高斯集合.
p的简系（简化剩余系）的集合，那么称Sp?12为模
例如
?1,2,?,?和?2,4,?,p?1?都是模p的一个高斯集合.
p的一个高斯集合，那么对于任意的整数a, (a,p)?1,一定存在
是由a唯一确定的.即如果S是
由定义5. 3可知：如果S是模
s?S和???1,?1?使得a??s(modp)成立.并且进一步可得：s,?模
p的一个高斯集合，且s?s?(modp)，那么s?s?.
36
定理1. 23（高斯引理） 设
p是奇素数，a是任意与p互素的整数，且S是模
p的一个高斯集合，
那么对于任意的s?S，存在唯一的整数ua(s)?S,?a(s)??1,?1?，使得
as??a(s)ua(s)(modp).
并且
?a?m?p????a(s)?(?1)， ??s?S其中m是S中满足
?a(s)??1的s的个数.
证明 存在性显然成立，下面证唯一性. 由于S是模
p的一个高斯集合，设s, s'?S，如果ua(s)?ua(s')，则有
as'??a(s')ua(s')(modp) ??a(s')ua(s)(modp)
??a(s')?a(s)?a(s)ua(s)(modp)
??as(modp).
于是由
''(a,p)?1知，可将a从同余式两边消去得s??s(modp).但由于s, s?S，而若
s'??s(modp，则)s'??S，矛盾（因S?(?S)??）.因此必有s?s'(modp)，即有s?s'.
这说明对任意的s?S，存在唯一的整数ua(s)?S,?a(s)?{1,?1}使得
as?ua(s)?a(s)(modp).
对任意的与有
p互素的整数a，显然映射ua: s?ua(s)（对任何s?S）是S的一个置换，因此
?s??u(s).
as?Ss?S从而有
a(p?1)2?s =?as
s?Ss?S???a(s)ua(s)(modp)
s?S???a(s)?ua(s)(modp)
s?Ss?S 37
???a(s)?s(modp).
s?Ss?S
因(?s,p)?1，故可两边同除以?s得
s?Ss?S?a?(p?1)2???a(s)(modp). ?p??a??s?S由于同余式两端都是?1，所以有
?a?m?p????a(s)?(?1). ▋ ??s?S例1. 30 利用高斯引理计算勒让德符号解 取模11的一个高斯集合为S3??11.
??2,4,6,8,10?，则有
3?2 ?6(mod11)， 3?4 ?(?1)?10(mod11)， 3?6 ?(?1)?4(mod11)， 3?10?8(mod11).
因此有m?2个s?S使得?a(s)??1，所以??3?2??(?1)?1.也就是说，3是模11的二次剩余.事?11?实上
52?62?3(mod11)，即5,6是3模11的两个平方根. ▋
p是奇素数，则有
例1.31 设
?2?(p2?1)/8. ?p??(?1)??证明 取模
p的高斯集合为S?{1,2,3.?.p?1}，那么 2?2ss?S???2,4,?,p?1?.
由高斯引理得
?2?m?p??(?1)， ??其中有m是S中使得
?2(s)??1的s的个数.
38
如果1?2s?(p?1)如果
2，那么2s?S，因此有u2(s)?2s且?2(s)?1.
由于
(p?1)2?s2?p?，1那么1?p?2s?(p?1)，2因此p?2s?S.
,)因此有
且?2(s)??1u2(s)?p?2s.所以
2s??(p?2s)(mopdm是
S中使得
(p?1)2?2s?p?1的s的个数，即满足不等式关系
的正整数s的个数.
由于
(p?1)4?s?(p?1)2 (1.13.1)
p是奇素数，那么p关于模8同余于1,3,5,7之一.因此只需讨论下列四种情况.
（i） 如果
p?1(mod8)，可设p?8k?1，则(?1)2(p8/)1?4)1(?1)2(?kk1??s?S.另一方面，
满足(1.13.1)当且仅当
2k?1?s?4k.
2于是得m2???2k，?2??(?1)2k?1?(?1)2k(4k?1)?(?1)(p?1)/8.
?p?（ii） 如果
(pp?3(mod8)，设p?8k?3，即有(?1)2?1)/2?(?1)(2k?1)(4k?1)??1.另一方面，
s?S满足(5.2)当且仅当
2k?1?s?4k?1.
即m2???2k?1，于是?2??(?1)2k?1??1?(?1)(p?1)/8.
?p?(iii) 如果
p?5(mod8)，可设p?8k?5，则(?1)(p2?1)/2?)(4?(?1)(2k1k3)???1.另一方
面，s?S满足(1.13.1)当且仅当
2k?1?12?s?4k?2.
即m???2k?1,?2??(?1)2k?1??1.
?p?(iv) 如果
p?7(mod8), 可设p?8k?7，则(?1)(p2?1)/2k?1)?(?1)2(2k?3)(2?1.另一方
面，s?S满足(1.13.1)当且仅当
2k?2?s?4k?3.
39
即m2???2k?2,?2??(?1)2k?2?1?(?1)(p?1)/2. ▋
?p?为更方便快捷地计算Legendre，下面介绍高斯（Gauss）二次互反律. 定理1.24（高斯二次互反律） 设
p,q是两个互异的奇素数，则有
p?1q?1?p??q?2?2 ??(?1)?q??p????? 或
p?1q?1q??p?2?2??(?1)?q??p?.
????证明 证明分为六步. 设
p与q是互异的奇素数, 且令
R??a1?a?(pq?1)/2, (a,pq)?1?, S??a1?a?(pq?1)/2, (a,p)?1?.
T??q?1,q?2,?,q?(p?1)/2?, A??a. 则
a?R1) 2)
T是S的真子集, 且Rq?12?S?T.
A?(?1)?q???(modp). ?p?这是因为由1)得
A??a?a?Ra?S?T?a?a?a
?a?Sa?T(p?1)/2
??i?1?(q?1)p??i????2??k?0p?1?p?1?2??!?q?2?(q?3)/2p?1(q?3)/2p?1l?1?(kp?l)
(p?1)/2
??i?1i???lk?0l?1p?12?p?1???!?q2??p?12(modp)
?((p?1)!)(q?1)/2q(modp).
再由Wilson定理及Legendre符号性质定理iii)有(p?1)!??1(mod而得
?q?p), ???q(p?1)/2(modp), 从
?p? 40