Jacobi 符号

Jacobi 符号是 Legendre 符号的弱化版本，它是为了弥补 Legendre 符号的局限性而引出的，我们知道 Legendre 符号$\left(\dfrac{a}{p}\right)$的计算需要求出$a$的素因子分解式才能进行下去，但有时候对于较大的数的素因子分解求起来并不容易，因此提出 Jacobi 符号。

定义

设奇数$P > 1$，且奇数$P$有素因子分解$P = p_1 p_2 \cdots p_s$，$p_i$都是素数，定义整数$a$对$P$的 Jacobi 符号：

$$\left(\dfrac{a}{P}\right) = \left(\dfrac{a}{p_1}\right) \left(\dfrac{a}{p_2}\right) \cdots \left(\dfrac{a}{p_s}\right)$$

其中$\left(\dfrac{a}{p_i}\right)$是 Legendre 符号，当$P$是奇素数时，Jacobi 符号就是 Legendre 符号。

注意，Jacobi 符号$\left(\dfrac{a}{P}\right) = 1$未必表示二次同余方程$x^2 \equiv a \pmod{P}$有解！

性质

1. $\left(\dfrac{1}{P}\right) = 1$，当$(a, p) = 1$时，取值为$\pm 1$，当$(a, p) > 1$时，取值为$0$；
2. 完全积性函数，即$\forall a, b \in \Z, \left(\dfrac{ab}{P}\right) = \left(\dfrac{a}{P}\right) \left(\dfrac{b}{P}\right)$；
3. $\left(\dfrac{a}{P_1 P_2}\right) = \left(\dfrac{a}{P_1}\right) \left(\dfrac{a}{P_2}\right)$；
4. 若$a \equiv b \pmod{P}$，则$\left(\dfrac{a}{P}\right) = \left(\dfrac{b}{P}\right)$，特别地，$\left(\dfrac{a}{P}\right) = \left(\dfrac{a+kP}{P}\right), \forall k \in \Z$；
5. 当$(a, p) = 1$时，$\left(\dfrac{a}{P^2}\right) = \left(\dfrac{a^2}{P}\right) = 1$；

特殊点的取值

1. $\left(\dfrac{-1}{P}\right) = (-1)^{\frac{P-1}{2}} = \begin{cases} 1, & P \equiv 1 \pmod{4}; \\ -1, & P \equiv -1 \pmod{4}. \end{cases}$
   但是要注意，Euler 判别法则对 Jacobi 符号是不成立的，尽管对$a = -1$这一特例成立。
2. 当$a=2$时，$\left(\dfrac{2}{P}\right) = (-1)^{\frac{P^2-1}{8}} = \begin{cases} 1, P \equiv \pm 1 \pmod{8}; \\ -1, P \equiv \pm 3 \pmod{8}. \end{cases}$
   但是要注意，Gauss 引理对 Jacobi 符号是不成立的，尽管对$a=2$这一特例成立。

二次互反律

对 Jacobi 符号，有像 Legendre 符号那样的互反律成立：
设$P, Q$为两个互素的正奇数，则有
$\left( \frac{P}{Q} \right) \left( \frac{Q}{P} \right) = (-1)^{\frac{P-1}{2} \cdot \frac{Q-1}{2}} = \begin{cases} 1, P \equiv 1 \pmod{4} \text{ or } Q \equiv 1 \pmod{4}; \\ -1, P \equiv Q \equiv 3 \pmod{4}. \end{cases}$

上下节

• 上一节：二次互反律
• 下一节：二次同余方程