跳至內容

勒讓德符號

維基百科,自由的百科全書

勒讓德符號,或二次特徵,是一個由阿德里安-馬里·勒讓德在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]

歐拉在之前證明了如果a是二次剩餘(mod p),(a|p) = 1;如果a是二次非剩餘,(a|p) = -1;這個結論現在稱為歐拉準則

除了這個基本定義式以外,還有其它(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.(德文翻譯者), 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 

外部連結

[編輯]