雅可比符号

1. 定义

设 $m$ 是大于 $1$ 的奇数，其素因数分解为 $m=p_1{p}_2\dots p_k$（$p_i$ 可以相同）。 对于任意整数 $a$，雅可比符号 $\left(\frac{a}{m}\right)$ 定义为勒让德符号的乘积：

$$\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\dots \left(\frac{a}{p_k}\right)$$

注意：当 $m$ 为素数时，雅可比符号退化为勒让德符号。

2. 核心考点：与平方剩余的关系

这是雅可比符号最容易混淆的地方：

• 若 $\left(\frac{a}{m}\right)=-1$：则 $a$ 一定不是 模 $m$ 的平方剩余。
• 若 $\left(\frac{a}{m}\right)=1$：则 $a$ 不一定是 模 $m$ 的平方剩余。
  • 原因：可能是两个非平方剩余（即两个 $-1$）相乘得到了 $1$。
  • 例子：$\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=1$，但 $x^2\equiv 2(\mathrm{mod}15)$ 无解。

3. 广义性质

雅可比符号保留了勒让德符号的绝大多数性质，使得计算过程极其流畅：

1. 周期性：若 $a\equiv b(\mathrm{mod}m)$，则 $\left(\frac{a}{m}\right)=\left(\frac{b}{m}\right)$。
2. 完全积性：$\left(\frac{ab}{m}\right)=\left(\frac{a}{m}\right)\left(\frac{b}{m}\right)$。
3. 特殊值公式（形式完全一致）：
   • $\left(\frac{-1}{m}\right)=(-1{)}^{\frac{m-1}{2}}$
   • $\left(\frac{2}{m}\right)=(-1{)}^{\frac{m^2-1}{8}}$

4. 广义二次互反律

设 $m,n$ 都是奇数（不要求是素数），且 $(m,n)=1$，则：

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

口诀依然适用：只有当 $m,n$ 模 $4$ 都余 $3$ 时，互换变号；否则不变号。

5. 计算策略 (算法流程)

利用雅可比符号计算 $\left(\frac{a}{m}\right)$ 的最大优势在于：不需要对 $a$ 进行素因子分解。

标准步骤：

1. 取模：利用周期性，将分子 $a$ 减小到 $a\mathrm{mod}m$。
2. 提取因子 2：若分子是偶数，提取所有因子 $2$，利用 $\left(\frac{2}{m}\right)$ 公式处理，直到分子变为奇数。
3. 互反律翻转：利用广义二次互反律，交换分子分母。
4. 重复：重复步骤 1-3，直到分子为 $1$。

• 取模降维（分子比分母大时）： $(\frac{a}{p})=(\frac{a(\mathrm{mod}p)}{p})$

  • 比如 $(\frac{30}{7})$ 直接变成 $(\frac{2}{7})$。

• 拆分提取（遇到 -1 和 2）：

  • 提取 -1：$(\frac{-1}{p})=1$ 当且仅当 $p\equiv 1(\mathrm{mod}4)$。
  • 提取 2：$(\frac{2}{p})=1$ 当且仅当 $p\equiv \pm 1(\mathrm{mod}8)$ （即 $p$ 是 1, 7, 9, 15…）。
  • 提取平方数：$(\frac{s^2\cdot a}{p})=(\frac{a}{p})$，完全平方数直接扔掉！

• 翻转法则（二次互反律）——最重要！

  当 $p,q$ 都是奇素数时，我们要交换分子分母：

  • 一般情况（好人）：如果 $p,q$ 中至少有一个模 4 余 1，直接翻转： $(\frac{p}{q})=(\frac{q}{p})$
  • 特殊情况（坏人）：如果 $p,q$ 两个都是模 4 余 3，翻转要变号： $(\frac{p}{q})=-(\frac{q}{p})$

记忆

翻转：双三变号，其余照旧

• 如果 $p$ 和 $q$ 都是 $4k+3$（除以 4 余 3），翻转时就要加负号

提取 -1：一正三负

• 一正：余 1 $\to$ 结果是 1。三负：余 3 $\to$ 结果是 -1。

提取 2：一七得正，三五得负

• 看 $p$ 除以 8 的余数。一七得正：余 1 或 7 $\to$ 结果是 1。三五得负：余 3 或 5 $\to$ 结果是 -1。

---

计算示例

计算 $\left(\frac{339}{1979}\right)$（注：1979 是素数，但 339 是合数。如果只用勒让德符号，必须先分解 339；用雅可比符号则不需要）。

1. 互反律：$339\equiv 3(\mathrm{mod}4)$， $1979\equiv 3(\mathrm{mod}4)$。两者都余 3，变号。 $\left(\frac{339}{1979}\right)=-\left(\frac{1979}{339}\right)$
2. 取模：$1979\mathrm{mod}339=284$。 $=-\left(\frac{284}{339}\right)$
3. 提取因子：$284=4\times 71=2^2\times 71$。 $=-\left(\frac{4}{339}\right)\left(\frac{71}{339}\right)=-(1)\cdot \left(\frac{71}{339}\right)$
4. 互反律：$71\equiv 3(\mathrm{mod}4)$，$339\equiv 3(\mathrm{mod}4)$。变号。 $=-[-\left(\frac{339}{71}\right)]=\left(\frac{339}{71}\right)$
5. 取模：$339\mathrm{mod}71=55$。 $=\left(\frac{55}{71}\right)$
6. 互反律：$55\equiv 3(\mathrm{mod}4)$， $71\equiv 3(\mathrm{mod}4)$。变号。 $=-\left(\frac{71}{55}\right)$
7. 取模：$71\mathrm{mod}55=16$。 $=-\left(\frac{16}{55}\right)=-1$（因为 16 是完全平方数，值为 1）。

结果：$\left(\frac{339}{1979}\right)=-1$。