雅可比符號

在數論中，雅可比符號是勒讓德符號的一種推廣，首先由普魯士數學家卡爾·雅可比在1837年引進^[1]。雅可比符號在數論中的各個分支中都有應用，尤其是在計算數論的素性檢驗、大數分解以及密碼學中有重要作用。

定義

勒讓德符號${\displaystyle ({\tfrac {a}{p}})}$是對於所有的正整數 ${\displaystyle a}$ 和所有的素數 ${\displaystyle p}$ 定義的。

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0\\+1\\-1\end{cases}}}$	如果p整除a；
	如果存在整數 ${\displaystyle X}$ 使得 ${\displaystyle X^{2}\equiv a{\pmod {p}}}$ 且p不整除a
	如果不存在整數 ${\displaystyle X}$ 使得 ${\displaystyle X^{2}\equiv a{\pmod {p}}}$

.

；

.

.

當${\displaystyle ({\frac {a}{p}})=1}$ 時，稱${\displaystyle a}$ 是模${\displaystyle p}$的二次剩餘；當${\displaystyle ({\frac {a}{p}})=-1}$ 時，稱${\displaystyle a}$ 是模${\displaystyle p}$的二次非剩餘。

運用勒讓德符號計算時要將 ${\displaystyle a}$ 分解成標準形式，計算上十分麻煩，因此產生了雅可比符號：

設 ${\displaystyle m}$ 是一個正奇數，其質因數分解式為 ${\displaystyle m=\prod _{i=1}^{s}p_{i}}$，並且正整數 ${\displaystyle a}$ 滿足 ${\displaystyle (m,a)=1}$ 那麼定義${\displaystyle ({\frac {a}{m}})=\prod _{i=1}^{s}({\frac {a}{p_{i}}})}$。

參見

• 克羅內克符號，將雅可比符號推廣到任意自然數上。