勒让德符号

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义[编辑]

勒让德符号(\tfrac{a}{p})(有时为了印刷上的方便,写成(a|p)),对整数 a 和奇素数p(假设 ap 的最大公因子是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)

然后把pq互换。

艾森斯坦的一个证明[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, ……由递推公式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.

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

性质[编辑]

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

  • 
\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)
(它是一个完全积性函数。这个性质可以理解为:两个剩余或非剩余的乘积是剩余,一个剩余与一个非剩余的乘积是非剩余。)
  • 如果ab (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}

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

  • 如果pq是奇素数,则
\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.

相关函数[编辑]

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

注释[编辑]

  1. ^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
  2. ^ 在欧拉(1783年)和勒让德(1786年)的作品中有所讲述。首先由高斯在1796年证明,在DA(1801年)出版;arts. 107-144(第一个证明),253-262(第二个证明)
  3. ^ Lemmermeyer, p.xiv “即使在像双二次互反律的简单情况下,我们仍然需要区分四个不同的符号,即Z[i]中的二次和双二次剩余符号,Z中的勒让德符号,以及Z中的有理二次剩余符号……”
  4. ^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
  5. ^ Lemmermeyer p. 8
  6. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
  7. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
  8. ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
  9. ^ 在Lemmermeyer的最初四章有所讲述
  10. ^ Lemmermeyer, ex. p. 31, 1.34
  11. ^ Lemmermeyer, pp. 236 ff.
  12. ^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.

参考文献[编辑]

  • 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 
  • Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory(第二版), New York: Springer. 1990, ISBN 0-387-97329-X 

外部链接[编辑]