\(\S 4.4\) 雅可比符号

定义

设 \(m > 1\) 是正奇数，\(m = p_1 p_2 \cdots p_r\)（其中 \(p_i\) 是奇素数，可重复），\(\gcd(n, m) = 1\)，定义雅可比符号为：

\[ \left(\frac{n}{m}\right) = \prod_{i=1}^{r} \left(\frac{n}{p_i}\right) \]

其中 \(\left(\frac{n}{p_i}\right)\) 是勒让德符号。当 \(m=1\) 时，约定 \(\left(\frac{n}{1}\right) = 1\)。

注意：雅可比符号 \(\left(\frac{n}{m}\right) = 1\) 不保证 \(n\) 是模 \(m\) 的二次剩余。只有当 \(m\) 为素数时，两者才等价。

---

性质

雅可比符号继承勒让德符号的大部分性质：

(a) 周期性

若 \(a \equiv b \pmod{m}\)，则 \(\left(\dfrac{a}{m}\right) = \left(\dfrac{b}{m}\right)\)。

(b) 完全积性

\[ \left(\frac{ab}{m}\right) = \left(\frac{a}{m}\right)\left(\frac{b}{m}\right),\qquad \left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right) \]

(c) 补充律

\[ \left(\frac{-1}{m}\right) = (-1)^{\frac{m-1}{2}},\qquad \left(\frac{2}{m}\right) = (-1)^{\frac{m^2-1}{8}} \]

(d) 互反律

设 \(m, n\) 是大于 \(1\) 的互质正奇数，则

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

---

计算优势

雅可比符号的最大意义在于：计算勒让德符号时无需对分子做质因数分解。只需利用互反律反复翻转约化，即可高效计算。

例：计算 \(\left(\frac{1001}{9907}\right)\)（\(9907\) 是素数）。

若用勒让德符号，需分解 \(1001 = 7 \times 11 \times 13\)；而用雅可比符号可直接做互反律：

\[ \begin{aligned} \left(\frac{1001}{9907}\right) &= \left(\frac{9907}{1001}\right) \quad (\because\ 1001 \equiv 1 \pmod{4}) \\ &= \left(\frac{9907 \bmod 1001}{1001}\right) = \left(\frac{898}{1001}\right) \\ &= \left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right) = \left(\frac{449}{1001}\right) \\ &= \left(\frac{1001}{449}\right) = \left(\frac{103}{449}\right) = \left(\frac{449}{103}\right) \\ &= \left(\frac{37}{103}\right) = \left(\frac{103}{37}\right) = \left(\frac{29}{37}\right) \\ &= \left(\frac{37}{29}\right) = \left(\frac{8}{29}\right) = \left(\frac{2}{29}\right)^3 = -1 \end{aligned} \]