查看“︁Jacobi 符号”︁的源代码

[[分类:同余理论]]
[[分类:以 Jacobi 命名]]
{{InfoBox
|name=雅可比符号
|eng_name=Jacobi symbol
}}
'''<ins>雅可比</ins>符号'''('''Jacobi symbol''')是 [[Legendre 符号]]的一个延拓。
可以用于计算 Legendre 符号的取值，并进而判断数字较大的[[二次剩余]]，或者说判断数字较大的[[二次同余方程]]是否有解。

== 定义 ==

对整数 <math>a</math> 和正奇数 <math>n</math> ，有标准质因数分解 <math>n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}</math> ， 则记

<math>\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>

等式的右侧是 Legendre 符号之积。

== 意义 ==

当 <math>n</math> 是质数时， Jacobi 符号就是 Legendre 符号。

通常情况下， Jacobi 符号不是 Legendre 符号，取 1 不代表对应的二次同余方程 <math>x^2 \equiv a \pmod n</math> 有解。但反过来，这一二次同余方程有解意味着全部 <math>x^2 \equiv a \pmod {p_i}</math> 都有相同解，即 Legendre 符号 <math>\left(\tfrac{a}{p_i}\right) = 1</math> ，此时有 Jacobi 符号 <math>\left(\tfrac{a}{n}\right) = \prod_{i=1}^k \left(\tfrac{a}{p_i}\right)^{\alpha_i} = 1</math> 。

Jacobi 符号的性质可以用于较快地计算出涉及较大数字的 Legendre 符号，这一过程中下面的操作数不是 Legendre 符号的模，因此不要求一直取得质数。

== 性质 ==

性质：
* 当 <math>\operatorname{gcd}(a, n)=1</math> 时， <math>\left(\tfrac{a}{n}\right)</math> 取值 <math>\pm1</math> ；否则 <math>\left(\tfrac{a}{n}\right)=0</math> 。
* [[完全乘性函数|完全乘性]]
** 对 <math>a</math>：
*** <math>\left(\frac{1}{n}\right) = 1</math>
*** <math>\left(\frac{ab}{n}\right) =  \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)</math>
** 对 <math>n</math>：
*** <math>\left(\frac{a}{1}\right) = 1</math> （[[空积]]）
*** <math>\left(\frac{a}{mn}\right) =  \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)</math>
* <math>\left(\frac{a}{n}\right) = \left(\frac{a \pm n}{n}\right)</math>
* 若 <math>\operatorname{gcd}(a,n)=1</math> ，则 <math>\left(\tfrac{a^2}{n}\right) = \left(\tfrac{a}{n^2}\right) = 1</math>
* 若 <math>m,n</math> 都是奇质数， <math>\left(\tfrac{m}{n}\right)\left(\tfrac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\frac{n-1}{2}}</math>

对 <math>a</math> 的特殊值：
* <math>\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>\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> 。


{{同余理论}}