勒让德符号

**勒讓德符號**，或二次特徵，是一個由阿德里安 - 馬里・勒讓德在 1798 年嘗試證明二次互反律時引入的函數。這個符號是許多高次剩餘符號的原型；其它延伸和推廣包括雅可比符號、克羅內克符號、希爾伯特符號，以及阿廷符號。

## 定義

勒讓德符號 $({\tfrac {a}{p}})$ （有時為了印刷上的方便，寫成 (_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} 代替。

## 勒讓德符號的公式

勒讓德原先把他的符號定義為：

　
: $\left({\frac {a}{p}}\right)=\pm 1\equiv a^{\frac {p-1}{2}}{\pmod {p}}.$

歐拉在之前證明了這個表達式是≡ 1 (mod _p_)，如果 _a_ 是二次剩餘 (mod _p_)，是≡ −1 如果 _a_ 是二次非剩餘；這個結論現在稱為歐拉準則。

除了這個基本公式以外，還有許多其它 (_a_|_p_) 的表達式，它們當中有許多都在二次互反律的證明中有所使用。

高斯證明了如果 $\zeta =e^{\frac {2\pi i}{p}}$ ，那麼：

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

這是他對二次互反律的第四個、第六個，以及許多後續的證明的基礎。參見高斯和。

克羅內克的證明是建立了

　
: $\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)$

然後把 _p_ 和 _q_ 互換。

艾森斯坦的一個證明是從以下等式開始：

　
: $\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.$
> 
> 

這個結果來自盧卡斯數列的理論，在素性測試中有所應用。參見沃爾 - 孫 - 孫素數。

## 性質

勒讓德符號有許多有用的性質，可以用來加速計算。它們包括：

 * $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$ （它是一個完全積性函數。這個性質可以理解為：兩個剩餘或非剩餘的乘積是剩餘，一個剩餘與一個非剩餘的乘積是非剩餘。）
* 如果 _a_ ≡ _b_ (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)^{\frac {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)^{\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}}$

這個性質稱為二次互反律的第二補充。一般的二次互反律為：

* 如果 _p_ 和 _q_ 是奇素數，則 $\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{\pmod {5}}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}\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.$

## 相關函數

* 雅可比符號是勒讓德符號的一個推廣，允許底數為合數，但底數仍然必須是奇數和正數。這個推廣提供了計算所有勒讓德符號的一個有效的方法。
* 一個進一步的推廣是克羅內克符號，把底數的範圍延伸到一切整數。

## 注釋

## 參考文獻

* 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
* Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, 1966, ISBN 0-262-02405-5
* Lemmermeyer, Franz, Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, 2000, ISBN 3-540-66957-4
* Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory（第二版）, New York: Springer, 1990, ISBN 0-387-97329-X
* Ribenboim, Paulo, The New Book of Prime Number Records, New York: Springer, 1996, ISBN 0-387-94457-5

## 外部連結

* 雅可比符號計算器