勒让德符号

维基百科，自由的百科全书

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

[编辑] 定义

勒让德符号 $(\tfrac{a}{p})$ （有时为了印刷上的方便，写成(a|p)），对整数 a 和奇素数p（假设 a 和 p 的最大公因子是1）有下列定义：

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

$\left(\frac{a}{p}\right) =\pm1\equiv a^{(p-1)/2}\pmod p.$

欧拉在之前证明了这个表达式是≡ 1 (mod p)，如果a是二次剩余(mod p)，是≡ −1如果a是二次非剩余；这个结论现在称为欧拉准则。

除了这个基本公式以外，还有许多其它(a|p)的表达式，它们当中有许多都在二次互反律的证明中有所使用。

高斯证明了^[6]如果 $\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)}.$

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

克罗内克的证明^[10]是建立了

$\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互换。

艾森斯坦的一个证明^[11]是从以下等式开始：

$\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 \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.$

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

[编辑] 性质

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

$\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)^{(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)^{(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{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)^\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.$

[编辑] 相关函数

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

[编辑] 注释

^ 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 & H.（德文翻译者） Maser (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory)（第二版）, New York: Chelsea, ISBN 0-8284-0191-8

Gauss, Carl Friedrich & Arthur A.（英文翻译者） Clarke (1986), Disquisitiones Arithmeticae（第二，修订版）, New York: Springer, ISBN 0387962549

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

Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66967-4

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

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

[编辑] 外部链接

雅可比符号计算器

[_note-0] A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186

[_note-1] 在欧拉（1783年）和勒让德（1786年）的作品中有所讲述。首先由高斯在1796年证明，在DA（1801年）出版；arts. 107-144（第一个证明），253-262（第二个证明）

[_note-2] Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下，我们仍然需要区分四个不同的符号，即Z[i]中的二次和双二次剩余符号，Z中的勒让德符号，以及Z中的有理二次剩余符号……”

[_note-KimSong01-3] Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).

[_note-4] Lemmermeyer p. 8

[_note-5] Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92

[_note-6] Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495

[_note-7] Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505

[_note-8] 在Lemmermeyer的最初四章有所讲述

[_note-9] Lemmermeyer, ex. p. 31, 1.34

[_note-10] Lemmermeyer, pp. 236 ff.

[_note-11] Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]