雅可比符號

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

定義

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

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

.

；

.

.

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

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

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

參見

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

參考來源

• Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, 1996, ISBN 9780262024051 

• Lemmermeyer, Franz, Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, 2000, ISBN 9783540669579 

• Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, 1990, ISBN 0-387-97329-X 

• Gauss, Carl Friedrich; Maser, H. (translator into German), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, 1965, ISBN 0-8284-0191-8 

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, 1986, ISBN 0387962549 

外部連結

• Calculate Jacobi symbol gives a display like the ones in the examples.