Jacobi 符号
| 雅可比符号 | |
|---|---|
| 术语名称 | 雅可比符号 |
| 英语名称 | Jacobi symbol |
雅可比符号(Jacobi symbol)是勒让德符号的一个延拓。 可以用于计算勒让德符号的取值，并进而判断数字较大的二次剩余，或者说判断数字较大的二次同余方程是否有解。
定义
对整数 [math]\displaystyle{ a }[/math] 和正奇数 [math]\displaystyle{ n }[/math] ，有标准质因数分解 [math]\displaystyle{ n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} }[/math] ， 则记
[math]\displaystyle{ \left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1} \left(\frac{a}{p_2}\right)^{\alpha_2} \dots \left(\frac{a}{p_k}\right)^{\alpha_k} }[/math]
等式的右侧是勒让德符号之积。
意义
当 [math]\displaystyle{ n }[/math] 是质数时，雅可比符号就是勒让德符号。
通常情况下，雅可比符号不是勒让德符号，取 1 不代表对应的二次同余方程 [math]\displaystyle{ x^2 \equiv a \pmod n }[/math] 有解。但反过来，这一二次同余方程有解意味着全部 [math]\displaystyle{ x^2 \equiv a \pmod {p_i} }[/math] 都有相同解，即勒让德符号 [math]\displaystyle{ \left(\tfrac{a}{p_i}\right) = 1 }[/math] ，此时有雅可比符号 [math]\displaystyle{ \left(\tfrac{a}{n}\right) = \prod_{i=1}^k \left(\tfrac{a}{p_i}\right)^{\alpha_i} = 1 }[/math] 。
雅可比符号的性质可以用于较快地计算出涉及较大数字的勒让德符号，这一过程中下面的操作数不是勒让德符号的模，因此不要求一直取得质数。
性质
性质：
- 当 [math]\displaystyle{ \operatorname{gcd}(a, n)=1 }[/math] 时， [math]\displaystyle{ \left(\tfrac{a}{n}\right) }[/math] 取值 [math]\displaystyle{ \pm1 }[/math] ；否则 [math]\displaystyle{ \left(\tfrac{a}{n}\right)=0 }[/math] 。
- 完全乘性
- 对 [math]\displaystyle{ a }[/math]：
- [math]\displaystyle{ \left(\frac{1}{n}\right) = 1 }[/math]
- [math]\displaystyle{ \left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right) }[/math]
- 对 [math]\displaystyle{ n }[/math]：
- [math]\displaystyle{ \left(\frac{a}{1}\right) = 1 }[/math] （空积）
- [math]\displaystyle{ \left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right) }[/math]
- 对 [math]\displaystyle{ a }[/math]：
- [math]\displaystyle{ \left(\frac{a}{n}\right) = \left(\frac{a \pm n}{n}\right) }[/math]
- 若 [math]\displaystyle{ \operatorname{gcd}(a,n)=1 }[/math] ，则 [math]\displaystyle{ \left(\tfrac{a^2}{n}\right) = \left(\tfrac{a}{n^2}\right) = 1 }[/math]
- 若 [math]\displaystyle{ m,n }[/math] 都是奇质数， [math]\displaystyle{ \left(\tfrac{m}{n}\right)\left(\tfrac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\frac{n-1}{2}} }[/math]
对 [math]\displaystyle{ a }[/math] 的特殊值：
- [math]\displaystyle{ \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 &, p\equiv 1 \pmod 4 \\ -1 &, p \equiv 3 \pmod 4 \end{cases} }[/math] ；
- [math]\displaystyle{ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 &, p\equiv \pm1 \pmod 8 \\ -1 &, p \equiv \pm3 \pmod 8 \end{cases} }[/math] 。