Jacobi Symbol

Motivation

The Legendre symbol

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

is defined only when the denominator is an odd prime. In many problems, however, one must work modulo an odd composite integer. The Jacobi symbol extends the notation of the Legendre symbol to this broader setting.

Let

n>1

be an odd integer with prime factorization

n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}.

For any integer $a$ , the Jacobi symbol is defined by

\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \left(\frac{a}{p_2}\right)^{e_2} \cdots \left(\frac{a}{p_r}\right)^{e_r}.

When $n$ is prime, the Jacobi symbol agrees with the Legendre symbol.

First Examples

Consider

\left(\frac{5}{21}\right).

Since

21=3\cdot7,

we have

\left(\frac{5}{21}\right) = \left(\frac{5}{3}\right) \left(\frac{5}{7}\right).

Now

5\equiv2\pmod3,

and $2$ is not a square modulo $3$ , so

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

Also

5\not\equiv 1,2,4\pmod7,

\left(\frac{5}{7}\right)=-1.

Therefore

\left(\frac{5}{21}\right)=(-1)(-1)=1.

This does not necessarily mean that $5$ is a square modulo $21$ . Indeed, a Jacobi symbol equal to $1$ is only a necessary condition for being a quadratic residue modulo a composite modulus, not a sufficient one.

Difference from the Legendre Symbol

For an odd prime $p$ , the value

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

means that

x^2\equiv a\pmod p

has a solution.

For composite $n$ , the value

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

does not guarantee that

x^2\equiv a\pmod n

has a solution.

For example,

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

But $2$ is not a square modulo $15$ . The squares modulo $15$ are

0,1,4,6,9,10.

Thus the Jacobi symbol behaves like a residue character, but it does not fully solve quadratic congruences for composite moduli.

Basic Properties

The Jacobi symbol inherits many formal properties from the Legendre symbol.

First, it depends only on $a\pmod n$ :

a\equiv b\pmod n \quad\Longrightarrow\quad \left(\frac{a}{n}\right)=\left(\frac{b}{n}\right).

Second, it is multiplicative in the numerator:

\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right) \left(\frac{b}{n}\right).

Third, it is multiplicative in the denominator:

\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right) \left(\frac{a}{n}\right)

for odd positive integers $m,n$ .

These properties make the Jacobi symbol computationally efficient.

Special Values

The special formulas for $-1$ and $2$ remain valid for odd positive $n$ :

\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2},

and

\left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8}.

Thus

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

when

n\equiv1\pmod4,

and equals $-1$ when

n\equiv3\pmod4.

Similarly,

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

when

n\equiv1,7\pmod8,

and equals $-1$ when

n\equiv3,5\pmod8.

Reciprocity Law

The Jacobi symbol satisfies the same formal reciprocity law as the Legendre symbol.

If $m$ and $n$ are odd positive coprime integers, then

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

Equivalently,

\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right)

unless both $m$ and $n$ are congruent to $3\pmod4$ . In that exceptional case,

\left(\frac{m}{n}\right) = -\left(\frac{n}{m}\right).

This law allows rapid computation without factoring the numerator.

Example of Computation

Compute

\left(\frac{1001}{9907}\right).

Using reciprocity is far better than checking squares directly.

Reduce:

1001=7\cdot11\cdot13.

Then

\left(\frac{1001}{9907}\right) = \left(\frac{7}{9907}\right) \left(\frac{11}{9907}\right) \left(\frac{13}{9907}\right).

Each symbol can be reduced by quadratic reciprocity and modular reduction. This process eventually reduces the computation to small symbols such as

\left(\frac{1}{q}\right),\qquad \left(\frac{-1}{q}\right),\qquad \left(\frac{2}{q}\right).

The Euclidean-algorithm-like nature of this process is one reason the Jacobi symbol is useful in computation.

Use in Primality Testing

The Jacobi symbol is central in probabilistic primality tests.

For an odd integer $n$ , Euler’s criterion suggests that if $n$ is prime, then

a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)\pmod n

for all integers $a$ coprime to $n$ .

If this congruence fails for some $a$ , then $n$ is definitely composite.

This idea leads to the Solovay-Strassen primality test. The test does not prove primality in one step, but it efficiently detects many composite numbers.

Conceptual Role

The Jacobi symbol separates formal reciprocity from actual solvability of quadratic congruences. It preserves the algebraic laws of the Legendre symbol while allowing composite denominators.

This distinction is important. For prime moduli, quadratic residue theory is controlled by fields. For composite moduli, the arithmetic decomposes through prime powers, and a single symbol no longer captures all information.

The Jacobi symbol is therefore both a computational tool and a bridge from elementary congruence theory to deeper arithmetic characters.