勒讓德符號

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

## 定義

設$a$是一個整數，$p$是一個奇素數，勒讓德符號$(\tfrac{a}{p})$（有時為了印刷上的方便，寫成(a|p))有下列定義：

$\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}代替。

## 勒讓德符號的公式

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

$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}}\pmod p, \left(\frac{a}{p}\right) \in \{-1,1\}.$$

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

除了這個基本定義式以外，還有其它(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)^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]}.$$

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

克羅內克的證明是建立了

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

然後把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{p}{q} \right) \cdot \left( \frac{q}{p} \right) = (-1)^{\frac{ (p-1)(q-1) }{4} }$

參見二次互反律和二次互反律的證明。

以下是一些較小的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.$$

## 相關函數

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