 Jacobi symbol

For an odd positive integer $n={\prod }_i{p}_i^{e_i}$, the Jacobi symbol is the product of Legendre symbolsThe fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when $a$ and $n$ have a common prime factor; otherwise it is $1$ or $-1$. For $n=1$, the empty product convention gives $(a/1)=1$.

If $a$ is a quadratic residue modulo $n$ and is coprime to $n$, its Jacobi symbol is one. The converse can fail for a composite number: $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, but two is not a square modulo fifteen because it is not a square modulo three.

Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.

The Jacobi symbol is a mathematical notation that generalizes the Legendre symbol. It is used primarily in number theory, particularly in the context of quadratic residues and the study of prime numbers.