勒讓德符號,或二次特徵,是一個由阿德里安-馬里·勒讓德在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]
![{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}},\left({\frac {a}{p}}\right)\in \{-1,1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e9ae7bf9e03010a40ce08acdde48fd7194649b5)
歐拉在之前證明了如果a是二次剩餘(mod p),(a|p) = 1;如果a是二次非剩餘,(a|p) = -1;這個結論現在稱為歐拉準則。
除了這個基本定義式以外,還有其它(a|p)的表達式,它們當中有許多都在二次互反律的證明中有所使用。
高斯證明了[6]如果
,那麼:
![{\displaystyle \left({\frac {a}{p}}\right)={\frac {1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a}}{1+\zeta +\zeta ^{4}+\zeta ^{9}+\dots +\zeta ^{(p-1)^{2}}}}={\frac {2(1+\zeta ^{a}+\zeta ^{4a}+\zeta ^{9a}+\dots +\zeta ^{(p-1)^{2}a})}{{\sqrt {p}}(1+i)[1+(-i)^{p}]}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/783ff164dffe529838a5998a905661e7ef518973)
這是他對二次互反律的第四個[7]、第六個[8],以及許多[9]後續的證明的基礎。參見高斯和。
克羅內克的證明[10]是建立了
![{\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb855773ec77763bc68495473b6fefff26e22d18)
然後把p和q互換。
艾森斯坦的一個證明[11]是從以下等式開始:
![{\displaystyle \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)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/114dc4c88125893e642b55a65e8aa89b6cc1396e)
把正弦函數用橢圓函數來代替,他也證明了三次和四次互反律。
其它含有勒讓德符號的公式
斐波那契數1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……由遞推公式F1 = F2 = 1,Fn+1 = Fn + Fn-1定義。
如果p是素數,則:
![{\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\;\;\;F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e181d4768c27c0211aa72c190c3de029ad791a7e)
例如:
![{\displaystyle ({\tfrac {2}{5}})=-1,\,\,F_{3}=2,F_{2}=1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff73e7a5b7e297cc026f6eb820aea916e66df5c)
![{\displaystyle ({\tfrac {3}{5}})=-1,\,\,F_{4}=3,F_{3}=2,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddb09711de46633a3aed5eb8c7645fd82c6d018e)
![{\displaystyle ({\tfrac {5}{5}})=\;\;\,0,\,\,F_{5}=5,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9590479e8a36276e7200a270774c51af114127cc)
![{\displaystyle ({\tfrac {7}{5}})=-1,\,\,F_{8}=21,\;\;F_{7}=13,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/690f49d30be9715186b6b16bbfd955dd19143466)
![{\displaystyle ({\tfrac {11}{5}})=+1,F_{10}=55,F_{11}=89.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/667113c068487285ac767f49eef07de6a4f19a2e)
這個結果來自盧卡斯數列的理論,在素性測試中有所應用。[12]參見沃爾-孫-孫素數。
性質
勒讓德符號有許多有用的性質,可以用來加速計算。它們包括:
(它是一個完全積性函數。這個性質可以理解為:兩個剩餘或非剩餘的乘積是剩餘,一個剩餘與一個非剩餘的乘積是非剩餘。)
- 如果a ≡ b (mod p),則
![{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22c53d660aed6373e99b8e0feb7d9801186b2d41)
![{\displaystyle \left({\frac {a^{2}}{p}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5b6f43df4f40202dbf365146ae39d7037387df5)
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd3bcfb31b3ac3ef72a6838ba0d0c58a2f236f74)
這個性質稱為二次互反律的第一補充。
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d90e3a78bfe75d1c4f4bfdd49690bd3af4673562)
這個性質稱為二次互反律的第二補充。一般的二次互反律為:
- 如果p和q是奇素數,則
![{\displaystyle \left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/966e6a0e5a66971e0c4d850b4a1627a598863d46)
參見二次互反律和二次互反律的證明。
以下是一些較小的p的值的公式:
- 對於奇素數p,
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d1c563452f82cfaf77baaecb82ed16888381a6b)
- 對於奇素數p,
![{\displaystyle \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{\pmod {5}}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}\end{cases}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e1ed5877d9a39798e4afdb699e61d13b8071e59)
但一般直接把剩餘和非剩餘列出更簡便:
- 對於奇素數p,
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a70b4a7cc4d99b0842fa9b6bc71209398f6f8eeb)
勒讓德符號(a|p)是一個狄利克雷特徵(mod p)。
計算例子
以上的性質,包括二次互反律,可以用來計算任何勒讓德符號。例如:
![{\displaystyle \left({\frac {12345}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827ce8eb12cd064d538fba78851cdcf32f5237e9)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/239c0bd33998501f6f040a0a53f0757f665b1cb8)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27dfd260354631933b8f1a96998af6093847c45)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827eecd5ac37c8bb9f0e1708f0752d2741785690)
![{\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15893c92c8e69189b6dbe3fc84878f80016cf56)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f3d05e8faa1196ae844ff490e380543cf4cd9d)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ab36b474cf5d1e547a7c818815d1588f528dcff)
![{\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cf73f630b227bdea61d980f4d945bb8fc2dfafc)
相關函數
- 雅可比符號是勒讓德符號的一個推廣,允許底數為合數,但底數仍然必須是奇數和正數。這個推廣提供了計算所有勒讓德符號的一個有效的方法。
- 一個進一步的推廣是克羅內克符號,把底數的範圍延伸到一切整數。
註釋
- ^ 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; 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
外部連結