勒让德符号

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

定义

勒让德符号(有时为了印刷上的方便,写成(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}代替。[4]

勒让德符号的公式

勒让德原先把他的符号定义为:[5]

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

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

高斯证明了[6]如果,那么:

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

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

然后把pq互换。

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

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

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

斐波那契数1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……由递推公式F1 = F2 = 1,Fn+1 = Fn + Fn-1定义。

如果p是素数,则:

例如:

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

性质

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

  • (它是一个完全积性函数。这个性质可以理解为:两个剩余或非剩余的乘积是剩余,一个剩余与一个非剩余的乘积是非剩余。)
  • 如果ab (mod p),则

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

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

  • 如果pq是奇素数,则

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

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

  • 对于奇素数p
  • 对于奇素数p

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

  • 对于奇素数p

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

计算例子

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

相关函数

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

注释

  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.(德文翻译者), , New York: Chelsea, 1965, ISBN 0-8284-0191-8
  • Gauss, Carl Friedrich; Clarke, Arthur A.(英文翻译者), , New York: Springer, 1986, ISBN 0387962549
  • Bach, Eric; Shallit, Jeffrey, , Cambridge: The MIT Press, 1966, ISBN 0-262-02405-5
  • Lemmermeyer, Franz, , Berlin: Springer, 2000, ISBN 3-540-66957-4
  • Ireland, Kenneth; Rosen, Michael, , New York: Springer, 1990, ISBN 0-387-97329-X
  • Ribenboim, Paulo, , New York: Springer, 1996, ISBN 0-387-94457-5

外部链接

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.