Jacobi

Returns the Jacobi symbol. The Jacobi symbol is a generalization of the Legendre symbol. For any integer $a$ and any positive odd integer $n$, the Jacobi symbol $\left(\frac{a}{n}\right)$ is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{{\alpha }_1}{\left(\frac{a}{p_2}\right)}^{{\alpha }_2}\cdots {\left(\frac{a}{p_k}\right)}^{{\alpha }_k}$

where $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ is the prime factorization of $n$.

The Legendre symbol $\left(\frac{a}{p}\right)$ is defined for all integers $a$ and all odd primes $p$ by

$\left(\frac{a}{p}\right)=\left\{\begin{array}{l}\begin{array}{l}-1\mathrm{if}a\not\equiv 0(\mathrm{mod}p)\mathrm{and}\mathrm{there}\mathrm{is}\mathrm{no}\mathrm{integer}x:a\equiv x^2\mathit{}(\mathrm{mod}p),\\ 0\mathrm{if}a\equiv 0(\mathrm{mod}p),\end{array}\\ 1\mathrm{if}a\not\equiv 0(\mathrm{mod}p)\mathrm{and}\mathrm{for}\mathrm{some}\mathrm{integer}x:a\equiv x^2(\mathrm{mod}p).\end{array}\right.$

jacobi(Integer, Integer)

Description

Given two integers $a$ and $n$, returns the Jacobi symbol $\left(\frac{a}{p}\right)$.