勒让德符号，或二次特征，是一个由阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数^[1][2]。这个符号是许多高次剩余符号的原型^[3]；其它延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号，以及阿廷符号。

定义

勒让德符号${\displaystyle ({\tfrac {a}{p)))}$（有时为了印刷上的方便，写成(a|p))有下列定义：

${\displaystyle \left({\frac {a}{p))\right)={\begin{cases}\quad 0\\+1\\-1\end{cases))}$	${\displaystyle \quad }$	如果${\displaystyle a\equiv 0{\pmod {p))}$
		如果${\displaystyle a\not \equiv 0{\pmod {p))}$，且对于某个整数${\displaystyle x,x^{2}\equiv \;a{\pmod {p))}$
		如果不存在整数${\displaystyle x}$，使得${\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]

${\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]如果${\displaystyle \zeta =e^{\frac {2\pi 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]是建立了

${\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]是从以下等式开始：

${\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, ……由递推公式F₁ = F₂ = 1，F_n+1 = F_n + F_n-1定义。

如果p是素数，则：

${\displaystyle F_{p-\left({\frac {p}{5))\right)}\equiv 0{\pmod {p)),\;\;\;F_{p}\equiv \left({\frac {p}{5))\right){\pmod {p)).}$

例如：

${\displaystyle ({\tfrac {2}{5)))=-1,\,\,F_{3}=2,F_{2}=1,}$

${\displaystyle ({\tfrac {3}{5)))=-1,\,\,F_{4}=3,F_{3}=2,}$

${\displaystyle ({\tfrac {5}{5)))=\;\;\,0,\,\,F_{5}=5,}$

${\displaystyle ({\tfrac {7}{5)))=-1,\,\,F_{8}=21,\;\;F_{7}=13,}$

${\displaystyle ({\tfrac {11}{5)))=+1,F_{10}=55,F_{11}=89.}$

这个结果来自卢卡斯数列的理论，在素性测试中有所应用。^[12]参见沃尔-孙-孙素数。

性质

勒让德符号有许多有用的性质，可以用来加速计算。它们包括：

• ${\displaystyle \left({\frac {ab}{p))\right)=\left({\frac {a}{p))\right)\left({\frac {b}{p))\right)}$（它是一个完全积性函数。这个性质可以理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。）

• 如果a ≡ b (mod p)，则${\displaystyle \left({\frac {a}{p))\right)=\left({\frac {b}{p))\right)}$

• ${\displaystyle \left({\frac {a^{2)){p))\right)=1}$

• ${\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))}$

这个性质称为二次互反律的第一补充。

• ${\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是奇素数，则${\displaystyle \left({\frac {q}{p))\right)=\left({\frac {p}{q))\right)(-1)^((\frac {p-1}{2)){\frac {q-1}{2))}.}$

参见二次互反律和二次互反律的证明。

以下是一些较小的p的值的公式：

• 对于奇素数p，${\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，${\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，${\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)。

计算例子

以上的性质，包括二次互反律，可以用来计算任何勒让德符号。例如：

${\displaystyle \left({\frac {12345}{331))\right)}$

${\displaystyle =\left({\frac {3}{331))\right)\left({\frac {5}{331))\right)\left({\frac {823}{331))\right)}$

${\displaystyle =\left({\frac {3}{331))\right)\left({\frac {5}{331))\right)\left({\frac {161}{331))\right)}$

${\displaystyle =\left({\frac {3}{331))\right)\left({\frac {5}{331))\right)\left({\frac {7}{331))\right)\left({\frac {23}{331))\right)}$

${\displaystyle =(-1)\left({\frac {331}{3))\right)\left({\frac {331}{5))\right)(-1)\left({\frac {331}{7))\right)(-1)\left({\frac {331}{23))\right)}$

${\displaystyle =-\left({\frac {1}{3))\right)\left({\frac {1}{5))\right)\left({\frac {2}{7))\right)\left({\frac {9}{23))\right)}$

${\displaystyle =-\left({\frac {1}{3))\right)\left({\frac {1}{5))\right)\left({\frac {2}{7))\right)\left({\frac {3}{23))\right)^{2))$

${\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}$

相关函数

• 雅可比符号是勒让德符号的一个推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。
• 一个进一步的推广是克罗内克符号，把底数的范围延伸到一切整数。

注释

参考文献

• 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 

• Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, 1966, ISBN 0-262-02405-5 

• Lemmermeyer, Franz, Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, 2000, ISBN 3-540-66957-4 

• Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory（第二版）, New York: Springer, 1990, ISBN 0-387-97329-X 

• Ribenboim, Paulo, The New Book of Prime Number Records, New York: Springer, 1996, ISBN 0-387-94457-5 

外部链接

• 雅可比符号计算器