Legendre and Jacobi symbol calculator

How it works

For an odd prime $p$, the Legendre symbol $\left(\frac ap\right)$ is $1$ when $a$ is a nonzero square modulo $p$, $-1$ when it is not, and $0$ when $p$ divides $a$. Euler’s criterion computes it as $a^{(p-1)/2} \bmod p$. The Jacobi symbol extends it to odd $n = p_1 p_2 \cdots$ as the product $\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots$.

The Jacobi symbol can be computed without knowing the factors of $n$, much like Euclid’s algorithm: reduce $a$ modulo $n$; take out factors 2 using $\left(\frac 2n\right) = 1$ for $n \equiv \pm 1 \pmod 8$ and $-1$ for $n \equiv \pm 3 \pmod 8$; then swap top and bottom with quadratic reciprocity, which changes the sign only when both are $\equiv 3 \pmod 4$.

Beware: for composite $n$, $\left(\frac an\right) = 1$ does not mean that $a$ is a square ($\left(\frac{2}{15}\right) = 1$, yet $2$ is not a square modulo $15$). This gap is used by the Goldwasser-Micali encryption scheme, and comparing the symbol with $a^{(n-1)/2}$ is the Solovay-Strassen primality test.