Jacobi Symbol — Leandro Junes

Inputs

Integer

a

Any integer.

Positive odd denominator

n

Odd integer ≥ 1.

Jacobi is not Legendre For a prime

p

,

\left(\frac{a}{p}\right)=1

means

a

is a nonzero quadratic residue. For a composite

n

,

\left(\frac{a}{n}\right)=1

does not mean that. For example

\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=1

, yet

x^{2}\equiv 2\pmod{15}

has no solution.

Try

Result

—

Reciprocity steps

—

Rule	Symbol after the step	Sign factor	Running sign

Method

Definition. If $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of the positive odd integer $n$ , then

\left(\frac{a}{n}\right)=\prod_{i=1}^{r}\left(\frac{a}{p_i}\right)^{e_i},\qquad\left(\frac{a}{1}\right)=1.

Why factoring is unnecessary. This is the definition, not the algorithm. Like the Legendre symbol, the Jacobi symbol obeys the laws below, so it can be evaluated by a Euclid-like procedure that never factors $n$ . For example, $\left(\frac{2}{15}\right)$ : $15\equiv 7\pmod 8$ , so the supplementary law for 2 gives no sign change and $\left(\frac{2}{15}\right)=1$ at once, with no need to write $15=3\cdot 5$ . The factored computation above agrees.

Remove powers of 2. For positive odd $n$ :

\left(\frac{2}{n}\right)=(-1)^{(n^{2}-1)/8}=\begin{cases}1,&n\equiv 1,7\pmod 8,\\ -1,&n\equiv 3,5\pmod 8,\end{cases}\qquad\left(\frac{-1}{n}\right)=(-1)^{(n-1)/2}.

Each factor 2 removed from the numerator contributes this sign.

Apply quadratic reciprocity. For positive odd coprime $m$ and $n$ :

\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{(m-1)(n-1)/4}.

The sign changes exactly when $m\equiv n\equiv 3\pmod 4$ .

Reduce as in Euclid's algorithm. After swapping, replace the new numerator by its remainder modulo the new denominator and repeat. The numerator eventually reaches 0. If the last denominator is 1 the answer is the accumulated sign; otherwise it is 0, and that last denominator is $\gcd(a,n)>1$ . The procedure behaves like the Euclidean algorithm, so it handles very large integers without factoring the denominator.

Multiplicativity.

\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right),\qquad\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right).

Interpreting the value. For $n>1$ : $\left(\frac{a}{n}\right)=0$ exactly when $\gcd(a,n)>1$ . The value $-1$ certifies that $a$ is a quadratic nonresidue: if $a$ were a square modulo $n$ with $\gcd(a,n)=1$ , it would be a square modulo every prime $p$ dividing $n$ , so every Legendre symbol would be 1 and the product could not be $-1$ . The value $+1$ certifies nothing when $n$ is composite: two nonresidues modulo different primes multiply to +1. If $n$ is prime the Jacobi symbol equals the Legendre symbol, and then $+1$ does mean that $a$ is a nonzero quadratic residue.

Difference from the Legendre symbol. The Legendre symbol requires a prime denominator and answers the residuosity question; the Jacobi symbol accepts any positive odd denominator and answers only the sign question above. This calculator does not test $n$ for primality and does not compute square roots.