勒让德符号 ，或二次特征 ，是一个由阿德里安-马里·勒让德 在1798年尝试证明二次互反律 时引入的函数[ 1] [ 2] [ 3] 雅可比符号 、克罗内克符号 、希尔伯特符号 ，以及阿廷符号 。
设
a
{\displaystyle a}
p
{\displaystyle p}
(
a
p
)
{\displaystyle ({\tfrac {a}{p}})}
a |p ))有下列定义：
(
a
p
)
=
{
0
+
1
−
1
{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 0\\+1\\-1\end{cases}}}
{\displaystyle \quad }
如果
a
≡
0
(
mod
p
)
{\displaystyle a\equiv 0{\pmod {p}}}
如果
a
≢
0
(
mod
p
)
{\displaystyle a\not \equiv 0{\pmod {p}}}
x
,
x
2
≡
a
(
mod
p
)
{\displaystyle x,x^{2}\equiv \;a{\pmod {p}}}
如果不存在整数
x
{\displaystyle x}
x
2
≡
a
(
mod
p
)
{\displaystyle x^{2}\equiv \;a{\pmod {p}}}
如果(a |p ) = 1，a 便称为二次剩余 (mod p )；如果(a |p ) = −1，则 a 称为二次非剩余 (mod p)。通常把零视为一种特殊的情况。
a 等于0、1、2、……时的周期数列 (a |p )，又称为勒让德数列 ，有时把{0,1,-1}的数值用{1,0,1}或{0,1,0}代替。[ 4]
勒让德原先把他的符号定义为：[ 5]
(
a
p
)
≡
a
p
−
1
2
(
mod
p
)
,
(
a
p
)
∈
{
−
1
,
1
}
.
{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}},\left({\frac {a}{p}}\right)\in \{-1,1\}.}
欧拉 在之前证明了如果a 是二次剩余(mod p )，(a |p ) = 1；如果a 是二次非剩余，(a |p ) = -1；这个结论现在称为欧拉准则 。
除了这个基本定义式以外，还有其它(a |p )的表达式，它们当中有许多都在二次互反律的证明中有所使用。
高斯证明了[ 6]
ζ
=
e
2
π
i
p
{\displaystyle \zeta =e^{\frac {2\pi i}{p}}}
(
a
p
)
=
1
+
ζ
a
+
ζ
4
a
+
ζ
9
a
+
⋯
+
ζ
(
p
−
1
)
2
a
1
+
ζ
+
ζ
4
+
ζ
9
+
⋯
+
ζ
(
p
−
1
)
2
=
2
(
1
+
ζ
a
+
ζ
4
a
+
ζ
9
a
+
⋯
+
ζ
(
p
−
1
)
2
a
)
p
(
1
+
i
)
[
1
+
(
−
i
)
p
]
.
{\displaystyle \left({\frac {a}{p}}\right)={\frac {1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a}}{1+\zeta +\zeta ^{4}+\zeta ^{9}+\dots +\zeta ^{(p-1)^{2}}}}={\frac {2(1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a})}{{\sqrt {p}}(1+i)[1+(-i)^{p}]}}.}
这是他对二次互反律的第四个[ 7] [ 8] [ 9] 高斯和 。
克罗内克的证明[ 10]
(
p
q
)
=
sgn
∏
i
=
1
q
−
1
2
∏
k
=
1
p
−
1
2
(
k
p
−
i
q
)
{\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)}
然后把p 和q 互换。
艾森斯坦的一个证明[ 11]
(
q
p
)
=
∏
n
=
1
p
−
1
2
sin
(
2
π
p
q
n
)
sin
(
2
π
p
n
)
.
{\displaystyle \left({\frac {q}{p}}\right)=\prod _{n=1}^{\frac {p-1}{2}}{\frac {\sin({\frac {2\pi }{p}}qn)}{\sin({\frac {2\pi }{p}}n)}}.}
把正弦函数用椭圆函数来代替，他也证明了三次和四次互反律。
斐波那契数 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……由递推公式F1 = F2 = 1，Fn+1 = Fn + Fn-1 定义。
如果p 是素数，则：
F
p
−
(
p
5
)
≡
0
(
mod
p
)
,
F
p
≡
(
p
5
)
(
mod
p
)
.
{\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\;\;\;F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}
例如：
(
2
5
)
=
−
1
,
F
3
=
2
,
F
2
=
1
,
{\displaystyle ({\tfrac {2}{5}})=-1,\,\,F_{3}=2,F_{2}=1,}
(
3
5
)
=
−
1
,
F
4
=
3
,
F
3
=
2
,
{\displaystyle ({\tfrac {3}{5}})=-1,\,\,F_{4}=3,F_{3}=2,}
(
5
5
)
=
0
,
F
5
=
5
,
{\displaystyle ({\tfrac {5}{5}})=\;\;\,0,\,\,F_{5}=5,}
(
7
5
)
=
−
1
,
F
8
=
21
,
F
7
=
13
,
{\displaystyle ({\tfrac {7}{5}})=-1,\,\,F_{8}=21,\;\;F_{7}=13,}
(
11
5
)
=
+
1
,
F
10
=
55
,
F
11
=
89.
{\displaystyle ({\tfrac {11}{5}})=+1,F_{10}=55,F_{11}=89.}
这个结果来自卢卡斯数列 的理论，在素性测试 中有所应用。[ 12] 沃尔-孙-孙素数 。
勒让德符号有许多有用的性质，可以用来加速计算。它们包括：
(
a
b
p
)
=
(
a
p
)
(
b
p
)
{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}
完全积性函数 。这个性质可以理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。）如果a ≡ b (mod p )，则
(
a
p
)
=
(
b
p
)
{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}
(
a
2
p
)
=
1
{\displaystyle \left({\frac {a^{2}}{p}}\right)=1}
(
−
1
p
)
=
(
−
1
)
p
−
1
2
=
{
+
1
if
p
≡
1
(
mod
4
)
−
1
if
p
≡
3
(
mod
4
)
{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1{\mbox{ if }}p\equiv 3{\pmod {4}}\end{cases}}}
这个性质称为二次互反律的第一补充。
(
2
p
)
=
(
−
1
)
p
2
−
1
8
=
{
+
1
if
p
≡
1
or
7
(
mod
8
)
−
1
if
p
≡
3
or
5
(
mod
8
)
{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}\end{cases}}}
这个性质称为二次互反律的第二补充。一般的二次互反律为：
如果p 和q 是奇素数，则
(
p
q
)
⋅
(
q
p
)
=
(
−
1
)
(
p
−
1
)
(
q
−
1
)
4
{\displaystyle \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}}
参见二次互反律 和二次互反律的证明 。
以下是一些较小的p 的值的公式：
对于奇素数p ，
(
3
p
)
=
(
−
1
)
⌈
p
+
1
6
⌉
=
{
+
1
if
p
≡
1
or
11
(
mod
12
)
−
1
if
p
≡
5
or
7
(
mod
12
)
{\displaystyle \left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}\end{cases}}}
对于奇素数p ，
(
5
p
)
=
(
−
1
)
⌊
p
−
2
5
⌋
=
{
+
1
if
p
≡
1
or
4
(
mod
5
)
−
1
if
p
≡
2
or
3
(
mod
5
)
,
{\displaystyle \left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}\end{cases}},}
但一般直接把剩余和非剩余列出更简便：
对于奇素数p ，
(
7
p
)
=
{
+
1
if
p
≡
1
,
3
,
9
,
19
,
25
,
or
27
(
mod
28
)
−
1
if
p
≡
5
,
11
,
13
,
15
,
17
,
or
23
(
mod
28
)
{\displaystyle \left({\frac {7}{p}}\right)={\begin{cases}+1{\mbox{ if }}p\equiv 1,3,9,19,25,{\mbox{ or }}27{\pmod {28}}\\-1{\mbox{ if }}p\equiv 5,11,13,15,17,{\mbox{ or }}23{\pmod {28}}\end{cases}}}
勒让德符号(a |p )是一个狄利克雷特征 (mod p )。
以上的性质，包括二次互反律，可以用来计算任何勒让德符号。例如：
(
12345
331
)
{\displaystyle \left({\frac {12345}{331}}\right)}
=
(
3
331
)
(
5
331
)
(
823
331
)
{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}
=
(
3
331
)
(
5
331
)
(
161
331
)
{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}
=
(
3
331
)
(
5
331
)
(
7
331
)
(
23
331
)
{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}
=
(
−
1
)
(
331
3
)
(
331
5
)
(
−
1
)
(
331
7
)
(
−
1
)
(
331
23
)
{\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}
=
−
(
1
3
)
(
1
5
)
(
2
7
)
(
9
23
)
{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}
=
−
(
1
3
)
(
1
5
)
(
2
7
)
(
3
23
)
2
{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}
=
−
(
1
)
(
1
)
(
1
)
(
1
)
=
−
1.
{\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}
雅可比符号 是勒让德符号的一个推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。一个进一步的推广是克罗内克符号 ，把底数的范围延伸到一切整数。
^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
^ 在欧拉（1783年）和勒让德（1786年）的作品中有所讲述。首先由高斯在1796年证明，在DA（1801年）出版；arts. 107-144（第一个证明），253-262（第二个证明）
^ Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下，我们仍然需要区分四个不同的符号，即Z [i]中的二次和双二次剩余符号，Z 中的勒让德符号，以及Z 中的有理二次剩余符号……”
^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24 , p. 343–348 (2001).
^ Lemmermeyer p. 8
^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
^ 在Lemmermeyer的最初四章有所讲述
^ Lemmermeyer, ex. p. 31, 1.34
^ Lemmermeyer, pp. 236 ff.
^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.
Gauss, Carl Friedrich; Maser, H.（德文翻译者）, Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory)（第二版）, New York: Chelsea, 1965, ISBN 0-8284-0191-8 Gauss, Carl Friedrich; Clarke, Arthur A.（英文翻译者）, Disquisitiones Arithmeticae（第二，修订版）, New York: Springer , 1986, ISBN 0387962549 Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory（第二版）, New York: Springer , 1990, ISBN 0-387-97329-X 
![{\displaystyle \left({\frac {a}{p}}\right)={\frac {1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a}}{1+\zeta +\zeta ^{4}+\zeta ^{9}+\dots +\zeta ^{(p-1)^{2}}}}={\frac {2(1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a})}{{\sqrt {p}}(1+i)[1+(-i)^{p}]}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/783ff164dffe529838a5998a905661e7ef518973)
