勒让德符号

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

定义

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

$\left(\frac{a}{p}\right)=\{\begin{array}{c}0\\ +1\\ -1\end{array}$	$$	如果$a\equiv 0(\mathrm{mod}p)$
		如果$a\equiv ̸0(\mathrm{mod}p)$，且对于某个整数$x,x^2\equiv a(\mathrm{mod}p)$
		如果不存在整数$x$，使得$x^2\equiv a(\mathrm{mod}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}}(\mathrm{mod}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{)}^{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]}.$

这是他对二次互反律的第四个、第六个，以及许多后续的证明的基础。参见高斯和。

克罗内克的证明是建立了

$\left(\frac{p}{q}\right)=\mathrm{sgn}\prod _{i=1}^{\frac{q-1}{2}}\prod _{k=1}^{\frac{p-1}{2}}(\frac{k}{p}-\frac{i}{q})$

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

如果p是素数，则：

$F_{p-\left(\frac{p}{5}\right)}\equiv 0(\mathrm{mod}p),F_p\equiv \left(\frac{p}{5}\right)(\mathrm{mod}p).$

例如：

$(\frac{2}{5})=-1,F_3=2,F_2=1,$

$(\frac{3}{5})=-1,F_4=3,F_3=2,$

$(\frac{5}{5})=0,F_5=5,$

$(\frac{7}{5})=-1,F_8=21,F_7=13,$

$(\frac{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{array}{c}+1\text{ if }p\equiv 1(\mathrm{mod}4)\\ -1\text{ if }p\equiv 3(\mathrm{mod}4)\end{array}$

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

• $\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{c}+1\text{ if }p\equiv 1\text{ or }7(\mathrm{mod}8)\\ -1\text{ if }p\equiv 3\text{ or }5(\mathrm{mod}8)\end{array}$

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

• 如果p和q是奇素数，则$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}.$

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

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

• 对于奇素数p，$\left(\frac{3}{p}\right)=(-1{)}^{\lceil \frac{p+1}{6}\rceil }=\{\begin{array}{c}+1\text{ if }p\equiv 1\text{ or }11(\mathrm{mod}12)\\ -1\text{ if }p\equiv 5\text{ or }7(\mathrm{mod}12)\end{array}$

• 对于奇素数p，$\left(\frac{5}{p}\right)=(-1{)}^{\lfloor \frac{p-2}{5}\rfloor }=\{\begin{array}{c}+1\text{ if }p\equiv 1\text{ or }4(\mathrm{mod}5)\\ -1\text{ if }p\equiv 2\text{ or }3(\mathrm{mod}5)\end{array},$

但一般直接把剩余和非剩余列出更简便：

• 对于奇素数p，$\left(\frac{7}{p}\right)=\{\begin{array}{c}+1\text{ if }p\equiv 1,3,9,19,25,\text{ or }27(\mathrm{mod}28)\\ -1\text{ if }p\equiv 5,11,13,15,17,\text{ or }23(\mathrm{mod}28)\end{array}$

勒让德符号(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.$

相关函数

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

参考文献

• Template:Citation

• Template:Citation

• Template:Citation

• Template:Citation

• Template:Citation

• Template:Citation

外部链接

• 雅可比符号计算器