雅可比符号

在数论中，雅可比符号是勒让德符号的一种推广，首先由普鲁士数学家卡尔·雅可比在1837年引进^[1]。雅可比符号在数论中的各个分支中都有应用，尤其是在计算数论的素性检验、大数分解以及密码学中有重要作用。

定义

勒让德符号 $({\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}}})$ 。

^ C.G.J.Jacobi "Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie", Bericht Ak. Wiss. Berlin (1837) pp 127-136

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