勒让德符号，或二次特征，是一个由阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数。这个符号是许多高次剩余符号的原型；其它延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号，以及阿廷符号。
定义
设a是一个整数，p是一个奇素数，勒让德符号(\tfrac{a}{p})（有时为了印刷上的方便，写成(a|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}代替。
勒让德符号的公式
勒让德原先把他的符号定义为：
:
\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)的表达式，它们当中有许多都在二次互反律的证明中有所使用。
高斯证明了如果\zeta = e^\frac{2\pi i}{p}，那么：
:
\left(\frac{a}{p}\right)
=\frac{1+\zeta^{a}+\zeta^{4a}+\zeta^{9a}+\dots+\zeta^{(p-1)^2a}}{1+\zeta+\zeta^{4}+\zeta^{9}+\dots+\zeta^{(p-1)^2}}
=\frac{2(1+\zeta^{a}+\zeta^{4a}+\zeta^{9a}+\dots+\zeta^{(p-1)^2a})}{\sqrt p(1+i)[1+(-i)^p]}.
这是他对二次互反律的第四个、第六个，以及许多后续的证明的基础。参见高斯和。
克罗内克的证明是建立了
:
\left(\frac{p}{q}\right)
=\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互换。
艾森斯坦的一个证明是从以下等式开始：
:
\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-\left(\frac{p}{5}\right)} \equiv 0 \pmod p,\;\;\;
F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.
例如：
:(\tfrac{2}{5}) = -1, \,\, F_3 = 2, F_2=1,
:(\tfrac{3}{5}) = -1, \,\, F_4 = 3,F_3=2,
:(\tfrac{5}{5}) = \;\;\,0,\,\, F_5 = 5,
:(\tfrac{7}{5}) = -1, \,\,F_8 = 21,\;\;F_7=13,
:(\tfrac{11}{5}) = +1, F_{10} = 55, F_{11}=89.
这个结果来自卢卡斯数列的理论，在素性测试中有所应用。参见沃尔-孙-孙素数。
性质
勒让德符号有许多有用的性质，可以用来加速计算。它们包括：
*
\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)
（它是一个完全积性函数。这个性质可以理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。）
如果a ≡ b (mod p*)，则
\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
*
\left(\frac{a^2}{p}\right) = 1
*
\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}
这个性质称为二次互反律的第一补充。
*
\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*是奇素数，则\left( \frac{p}{q} \right) \cdot \left( \frac{q}{p} \right) = (-1)^{\frac{ (p-1)(q-1) }{4} }
参见二次互反律和二次互反律的证明。
以下是一些较小的p的值的公式：
对于奇素数p*，
\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*，
\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 \pmod5 \\
-1\mbox{ if }p \equiv 2\mbox{ or }3 \pmod5 \end{cases},
但一般直接把剩余和非剩余列出更简便：
对于奇素数p*，
\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)。
计算例子
以上的性质，包括二次互反律，可以用来计算任何勒让德符号。例如：
:\left ( \frac{12345}{331}\right )
:=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right )
:=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right )
:=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right )
:= (-1) \left ( \frac{331}{3}\right ) \left ( \frac{331}{5}\right ) (-1) \left ( \frac{331}{7}\right ) (-1) \left ( \frac{331}{23}\right )
:=-\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{9}{23}\right )
:=-\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{3}{23}\right )^2
:= - \left (1\right ) \left (1\right ) \left (1\right ) \left (1\right ) = -1.
相关函数
*雅可比符号是勒让德符号的一个推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。
*一个进一步的推广是克罗内克符号，把底数的范围延伸到一切整数。
注释
参考文献
*
*
*
*
*
*
外部链接
*[https://web.archive.org/web/20080720165638/http://www.math.fau.edu/Richman/jacobi.htm 雅可比符号计算器]
评论 (0)