Jacobi 符号与 Legendre 符号 — Arendelle Royal Library

雅可比符号与勒让德符号

设 \(n\) 为正奇数，其素因子分解为

\(n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}\)

则 Jacobi 符号定义为

\(\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \left(\frac{a}{p_2}\right)^{e_2} \cdots \left(\frac{a}{p_r}\right)^{e_r}\)

右边的 \(\left(\frac{a}{p_i}\right)\) 是 Legendre 符号。因此 Jacobi 符号是把 Legendre 符号从模奇素数推广到模任意正奇数的结果。

当 \(n = p\) 为奇素数时，Jacobi 符号就退化为 Legendre 符号。

设 \(p\) 为奇素数，则 Legendre 符号

\(\left(\frac{a}{p}\right) = \begin{cases} 1, & a \text{ 是模 } p \text{ 的二次剩余} \\ -1, & a \text{ 是模 } p \text{ 的二次非剩余} \\ 0, & p \mid a \end{cases}\)

能够准确判断模 \(p\) 下的二次剩余性。

而 Jacobi 符号 \(\left(\frac{a}{n}\right)\) 在 \(n\) 为合数时含义变弱：

最关键的区别在于：

Legendre 符号的值 \(1\) 真正刻画了“是平方”；Jacobi 符号在合数模下取值 \(1\) 只是一种必要条件，不是充分条件。

\(\left(\frac{2}{15}\right) = \left(\frac{2}{3}\right)\left(\frac{2}{5}\right) = (-1)(-1) = 1\)

但模 \(15\) 的平方剩余只有 \(0,1,4,6,9,10\)，其中并不包含 \(2\)，所以 \(2\) 不是模 \(15\) 的平方剩余。

Jacobi 符号保留了 Legendre 符号的大部分形式性质：

模分子周期性：若 \(a \equiv b \pmod{n}\)，则 \(\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)\)
关于分子的完全乘性： \(\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)\)
关于分母的乘性：若 \(m,n\) 都是正奇数，则 \(\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)\)
与 \(-1,2\) 有关的公式：对正奇数 \(n\)， \(\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2}\) \(\left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8}\)

这些公式和 Legendre 符号完全同形，只是把奇素数 \(p\) 推广成了正奇数 \(n\)。

Jacobi 符号仍满足与 Legendre 符号相同形式的二次互反律：

若 \(m,n\) 为互素的正奇数，则

\(\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\frac{n-1}{2}}\)

因此它在计算上非常有用：即使 \(n\) 不是素数，也可以通过不断交换分子分母、配合约化和 \((2/n), (-1/n)\) 的公式，快速求出 Jacobi 符号。

这也是许多算法中使用 Jacobi 符号的重要原因，例如素性测试和二次剩余相关计算。

计算

\(\left(\frac{137}{227}\right)\)

由于 \(227\) 是奇素数，这里 Jacobi 符号和 Legendre 符号一致。但计算时完全可以按 Jacobi 符号的规则做：

\(\left(\frac{137}{227}\right) = \left(\frac{-90}{227}\right) = \left(\frac{-1}{227}\right)\left(\frac{9}{227}\right)\left(\frac{10}{227}\right)\)

其中

\(\left(\frac{-1}{227}\right) = -1\)，因为 \(227 \equiv 3 \pmod{4}\)；
\(\left(\frac{9}{227}\right) = 1\)；
\(\left(\frac{10}{227}\right) = \left(\frac{2}{227}\right)\left(\frac{5}{227}\right) = (-1)(-1) = 1\)。

因此

\(\left(\frac{137}{227}\right) = -1\)

这说明 \(137\) 不是模 \(227\) 的二次剩余。

Jacobi 和与 Jacobi 符号名字相近，但它们不是同一个概念。

它们的联系在于：当考虑有限域上的二次特征时，最基本的例子就是 Legendre 符号

\(\chi(x) = \left(\frac{x}{p}\right)\)

因此 Jacobi 和通常直接建立在 Legendre 符号所对应的二次特征 上，而不是建立在合数模的 Jacobi 符号上。