定义
设 p 是奇素数,gcd(n,p)=1,定义勒让德符号为:
(pn)={ 1−1若 n 是模 p 的二次剩余若 n 是模 p 的二次非剩余
当 p∣n 时,补充定义 (pn)=0。
由欧拉判别条件,立即有
(pn)≡n2p−1(modp)
性质
设 p 是奇素数,则勒让德符号满足:
(a) 周期性
若 a≡b(modp),则 (pa)=(pb)。直接由定义可得。
(b) 完全积性
(pab)=(pa)(pb).
证明
由欧拉判别条件:
(pab)≡(ab)2p−1=a2p−1⋅b2p−1≡(pa)(pb)(modp)
即
p∣(pab)−(pa)(pb)
而 (pab)−(pa)(pb) 的值域为 [−2,2],又 p>2,故这个差只能是 0。因此
(pab)=(pa)(pb)□
(c) 补充律一
(p−1)=(−1)2p−1={1,−1,p≡1(mod4),p≡3(mod4).
证明
由欧拉判别条件,(p−1)≡(−1)2p−1(modp)。
两边取值均在 {1,−1} 中,而 p>2,故
(p−1)=(−1)2p−1
当 p≡1(mod4) 时,2p−1 为偶数,(−1)2p−1=1;当 p≡3(mod4) 时,2p−1 为奇数,(−1)2p−1=−1。□
(d) 补充律二
(p2)=(−1)8p2−1={1,−1,p≡±1(mod8),p≡±3(mod8).
证明
显然我们可以得到:
(p2)=22p−1(modp)
所以我们证明的关键是判断 22p−1modp 这个数到底是 1 还是 −1
然后我们自然地想到:能否构造一个等式,使它的结果包含 22p−1,同时又有另一种容易判断符号的表达?
数列 {2,4,6,⋯,p−1} 恰好给出 2p−1 个 2,即
i=1∏2p−12i=22p−1⋅i=1∏2p−1i.
于是问题变成:i=1∏2p−12i 与 i=1∏2p−1i 之间有什么联系?
两者都有 2p−1 个数,但一个是 {2,4,⋯,p−1},另一个是 {1,2,⋯,2p−1}。
这时考虑绝对最小剩余。{2,4,⋯,p−1} 在模 p 下可以化为 {⋯,−3,−1,2,4,⋯},其中同样含有 {1,2,⋯,2p−1}。
这里略去了严谨性,后面高斯引理部分会补上完整证明。
假设化为绝对最小剩余后,负数有 k 个,则
i=1∏2p−12i=(−1)k⋅i=1∏2p−1i.
下面只需找出 k 与 p 的关系。
又 p 是奇素数, 所以绝对最小剩余是 {r∣−2p−1≤r≤2p−1}
(1) 2p−1 是奇数:
令 p=4t−1
那么从 2p+1 到 p−1 这 2p−1−2p+1+1=4p+1 个数都会变成负数, 所以 k=4p+1=t
(2) 2p−1 是偶数:
令 p=4t+1
那么类似地可以计算出 k=2p−1−2p+3+1=4p−1=t
分类讨论 t 的奇偶性即可得到 (−1)k。下面直接推出 8p2−1。
进一步研究
也就是说,我们想得到 k=k(p) 的具体表达式。
已知
k=⎩⎨⎧4p+1,4p−1,p≡−1(mod4),p≡1(mod4).
所以
(−1)k=⎩⎨⎧(−1)4p+1,(−1)4p−1,2p−1 为奇数,2p+1 为奇数.
显然 一个数的奇数次方是不改变符号的 , 那么
(−1)k=((−1)4p+1)2p−1=((−1)4p−1)2p+1=(−1)8p2−1
这次不再只分离绝对最小剩余之外的数,而是全部讨论。注意到
p−12p−34⋮p−2p−12p−1=1⋅(−1)(modp)=2⋅(−1)2(modp)=3⋅(−1)3(modp)=4⋅(−1)4(modp)=2p−1⋅(−1)2p−1(modp),若 2p−1 为奇数=2p−1⋅(−1)2p−1(modp),若 2p−1 为偶数
左右累乘,可得:
i=1∏2p−12i=i=1∏2p−1i⋅(−1)1+2+⋯+2p−1
所以最后有
k=2(1+2p−1)⋅2p−1=8p2−1.□
高斯引理
设 p 是一个奇素数, gcd(n,p)=1, 且 2p−1 个数 ⟨n⟩p,⟨2n⟩p,⋯,⟨(2p−1)n⟩p 中有 m 个大于 2p, 则 (pn)=(−1)m
证明
把 ⟨n⟩p,⟨2n⟩p,⋯,⟨2p−1n⟩p 中小于 2p 的数记为 a1,a2,⋯,as,大于 2p 的数记为 b1,b2,⋯,bm,其中 s+m=2p−1。