# Jacobi symbol

Recall that the second (lower) entry in the Legendre
symbol (*a*|*q*), also denoted , must be prime. Jacobi generalized the
Legendre symbol to allow lower entries that are odd (but
not necessarily prime) as follows: Let the factorization
of *n* be . Then

Notice that (*a*|1) = 1 for all integers *a*.

This new symbol (which looks just like the Legendre
symbol) is called the **Jacobi symbol**. Warning: For
the Jacobi symbol, (*a*|*n*)=1 does not
necessarily mean that *a* is a quadratic residue
of *n*. For example, (8|15) = 1, but 8 is not a
quadratic residue of 15.

The Jacobi symbol has many properties that make its
use the easiest way to evaluate a Legendre symbol.
Suppose *m* and *n* are positive odd integers,
and *a* and *b* are any integers. Then the
Jacobi symbol satisfies the following:

- (
*a*|*n*)=0 if gcd(*a*,*n*) > 1. - (-1|
*n*) = 1 if*n*≡ 1 (mod 4), and (-1|*n*) = -1 if*n*≡ 3 (mod 4); - (
*a*|*n*) (*b*|*n*) = (*ab*|*n*); - (
*a*|*m*) (*a*|*n*) = (*a*|*mn*); - if
*a*≡*b*(mod*n*), then (*a*|*n*) = (*b*|*n*).

For the prime 2 we have

- (2|
*n*) = 1 if*n*≡ 1 or 7 (mod 8), and - (2|
*n*) = -1 if*n*≡ 3 or 5 (mod 8).

Finally, and perhaps most usefully, if gcd(*a*,*n*) =1, and *a* is odd and positive,

In other words, (*a*|*n*)= (*n*|*a*),
unless *a* ≡ *n* ≡ 3 (mod 4), in which case
(*a*|*n*) = -(*n*|*a*).

This gives the following algorithm for finding
(*a*|*n*). Suppose *n* is odd and
0 < *a* < *n*:

`Jacobi(`

a,n) {j:= 1 while (anot 0) do { while (aeven) do {a:=a/2 if (n≡ 3 (mod 8) orn≡ 5 (mod 8)) thenj:= -j} interchange(a,n) if (a≡ 3 (mod 4) andn≡ 3 (mod 4)) thenj:= -ja:=amodn} if (n= 1) then return (j) else return(0) }

Notice that this is just an adaptation of the classical Euclidean algorithm.

**See Also:** QuadraticResidue, LegendreSymbol