查看“勒让德符号”的源代码

'''勒让德符号'''，或[[狄利克雷特征#例子|二次特征]]，是一个由[[阿德里安-马里·勒让德]]在1798年尝试证明[[二次互反律]]时引入的函数<ref>A. M. Legendre ''Essai sur la theorie des nombres'' Paris 1798, p 186</ref><ref>在欧拉（1783年）和勒让德（1786年）的作品中有所讲述。首先由高斯在1796年证明，在DA（1801年）出版；arts. 107-144（第一个证明），253-262（第二个证明）</ref>。这个符号是许多高次剩余符号的原型<ref>Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下，我们仍然需要区分四个不同的符号，即'''Z'''[i]中的二次和双二次剩余符号，'''Z'''中的勒让德符号，以及'''Z'''中的有理二次剩余符号……”</ref>；其它延伸和推广包括[[雅可比符号]]、[[克罗内克符号]]、[[希尔伯特符号]]，以及[[阿廷互反律|阿廷符号]]。

== 定义 ==

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

:{| border="0"
|rowspan=3|<math>\left(\frac{a}{p}\right) = \begin{cases}\quad 0\\ +1 \\ -1\end{cases}</math>
|rowspan=3|<math>\quad</math>
| 如果<math>a \equiv 0 \pmod{p}</math>
|-
| 如果<math>a \not\equiv 0\pmod{p}</math>，且对于某个整数<math>x, x^2\equiv \;a \pmod{p}</math>
|-
| 如果不存在整数<math>x</math>，使得<math>x^2 \equiv \;a \pmod{p}</math>。 
|}

如果(''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}代替。<ref name=KimSong01>Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," ''Designs, Codes, and Cryptography'' '''24''', p. 343–348 (2001).</ref>

== 勒让德符号的公式 ==

勒让德原先把他的符号定义为：<ref>Lemmermeyer p. 8</ref>

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

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

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

高斯证明了<ref>Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in ''Untersuchungen ...'' pp. 463-495. Crandall & Pomerance p. 92</ref>如果<math>\zeta = e^\frac{2\pi i}{p}</math>，那么：

:<math>
\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]}.
</math>

这是他对二次互反律的第四个<ref>Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in ''Untersuchungen ...'' pp. 463-495</ref>、第六个<ref>Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in ''Untersuchungen ...'' pp. 501-505</ref>，以及许多<ref>在Lemmermeyer的最初四章有所讲述</ref>后续的证明的基础。参见[[高斯和]]。

克罗内克的证明<ref>Lemmermeyer, ex. p. 31, 1.34</ref>是建立了
:<math>
\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)</math>
然后把''p''和''q''互换。

艾森斯坦的一个证明<ref>Lemmermeyer, pp. 236 ff.</ref>是从以下等式开始：
:<math>
\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)}.

</math>

把正弦函数用椭圆函数来代替，他也证明了三次和四次互反律。

=== 其它含有勒让德符号的公式 ===

[[斐波那契数]]1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……由递推公式F<sub>1</sub> = F<sub>2</sub> = 1，F<sub>n+1</sub> = F<sub>n</sub> + F<sub>n-1</sub>定义。

如果''p''是素数，则：

:<math>
F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p,\;\;\;
F_{p} \equiv \left(\frac{p}{5}\right) \pmod p. 
</math> 

<blockquote>
例如： 

:<math>(\tfrac{2}{5}) = -1, \,\, F_3  = 2, F_2=1,</math> 
:<math>(\tfrac{3}{5}) = -1, \,\, F_4  = 3,F_3=2,</math> 
:<math>(\tfrac{5}{5}) = \;\;\,0,\,\,  F_5  = 5,</math> 
:<math>(\tfrac{7}{5}) = -1,  \,\,F_8  = 21,\;\;F_7=13,</math> 
:<math>(\tfrac{11}{5}) = +1,  F_{10}  = 55, F_{11}=89.</math> 
</blockquote>

这个结果来自[[卢卡斯数列]]的理论，在[[素性测试]]中有所应用。<ref>Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.</ref>参见[[沃尔-孙-孙素数]]。

== 性质 ==

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

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

*如果''a'' ≡ ''b'' (mod ''p'')，则<math>
\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
</math>

*<math>
\left(\frac{a^2}{p}\right) = 1
</math>

*<math>
\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}</math>

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

*<math>
\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}</math>

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

*如果''p''和''q''是奇素数，则<math>
\left(\frac{q}{p}\right) 
= \left(\frac{p}{q}\right)(-1)^{ \frac{p-1}{2} \frac{q-1}{2} }.
</math> 

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

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

*对于奇素数''p''，<math>
\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}</math>

*对于奇素数''p''，<math>
\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},</math>

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

*对于奇素数''p''，<math>
\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}</math>

勒让德符号(''a''|''p'')是一个[[狄利克雷特征]](mod ''p'')。

== 计算例子 ==

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

:<math>\left ( \frac{12345}{331}\right )</math>

:<math>=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right )</math>

:<math>=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right )</math>

:<math>=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right )</math>

:<math>= (-1) \left ( \frac{331}{3}\right ) \left ( \frac{331}{5}\right ) (-1) \left ( \frac{331}{7}\right ) (-1) \left ( \frac{331}{23}\right )</math>

:<math>=-\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{9}{23}\right )</math>

:<math>=-\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{3}{23}\right )^2</math>

:<math>= - \left (1\right ) \left (1\right ) \left (1\right ) \left (1\right ) = -1.</math>

== 相关函数 ==

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

== 注释 ==
{{reflist}}

== 参考文献 ==

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Maser | first2 = H.（德文翻译者） 
  | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory)（第二版）
  | publisher = Chelsea
  | location = New York
  | date = 1965
  | isbn = 0-8284-0191-8}}

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Clarke | first2 = Arthur A.（英文翻译者）  
  | title = Disquisitiones Arithmeticae（第二，修订版）
  | publisher = [[Springer]]
  | location = New York
  | date = 1986
  | isbn = 0387962549}}

*{{citation
  | last1 = Bach  | first1 = Eric
  | last2 = Shallit | first2 = Jeffrey 
  | title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
  | publisher = [[The MIT Press]]
  | location = Cambridge
  | date = 1966
  | isbn =0-262-02405-5}}

*{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = [[Springer]]
  | location = Berlin
  | date = 2000
  | isbn =3-540-66957-4}}

*{{citation
  | last1 = Ireland  | first1 = Kenneth
  | last2 = Rosen  | first2 = Michael
  | title = A Classical Introduction to Modern Number Theory（第二版）
  | publisher = [[Springer]]
  | location = New York
  | date = 1990
  | isbn = 0-387-97329-X}}

*{{citation
  | last1 = Ribenboim  | first1 = Paulo
  | title = The New Book of Prime Number Records
  | publisher = [[Springer]]
  | location = New York
  | date = 1996
  | isbn = 0-387-94457-5}}

== 外部链接 ==
*[https://web.archive.org/web/20080720165638/http://www.math.fau.edu/Richman/jacobi.htm 雅可比符号计算器]

[[Category:二次剩余]]
[[Category:数学符号]]
[[Category:算术函数]]