Jacobi Symbol

The Jacobi symbol is a generalization of the Legendre symbol, which can be used to simplify computations involving quadratic residues. It shares many of the properties of the Legendre symbol, and can be used to state and prove an extended version of the law of quadratic reciprocity.

Recall that the Legendre symbol $\left( \frac{a}{p}\right)$ is defined for an integer $a$ and an odd prime $p.$ The Jacobi symbol $\left( \frac{a}{n} \right)$ is defined for any odd positive integer $n,$ as follows:

If $n = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k},$ where the $p_i$ are primes, then

$$\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{a_1} \left( \frac{a}{p_2} \right)^{a_2} \cdots \left( \frac{a}{p_k} \right)^{a_k}.$$

The Legendre symbol measures whether $a$ is a square mod $p.$ Unfortunately, the Jacobi symbol does not retain this property:

If $\text{gcd}(a,n) = 1$ and $a$ is a square mod $n,$ where $n$ is an odd positive integer, then $\left( \frac{a}{n} \right) = 1;$ but the converse is not true.

To see this, note that if $a$ is a square mod $n,$ then it is a square mod $p_i$ for all primes $p_i$ dividing $n,$ so the Legendre symbols $\left( \frac{a}{p_i} \right)$ are all equal to $1,$ so the Jacobi symbol equals $1$ by definition. But if $a$ is not a square mod $p_i$ for some $i,$ the Jacobi symbol might still be $1.$

• $\left(\dfrac{2}{9} \right) = \left( \dfrac23 \right)^2 = (-1)^2 = 1,$ but $2$ is not a square mod $9$ $($it is not even a square mod $3).$
• $\left( \dfrac{3}{35} \right) = \left( \dfrac35 \right) \left( \dfrac37\right) = (-1)(-1) = 1,$ but $3$ is not a square mod $35$ $($it is not a square mod $5$ or $7).$

On the other hand, many of the other properties of the Legendre symbol do extend to the Jacobi symbol.

Let $m,n$ be positive odd integers and let $a,b$ be integers.

1. If $a\equiv b \pmod n$, then $\left(\dfrac{a}{n}\right)=\left(\dfrac{b}{n}\right)$.
2. $\left(\dfrac{ab}{n}\right)=\left(\dfrac{a}{n}\right)\left(\dfrac{b}{n}\right)$; that is, the function $f(a) = \left(\dfrac{a}{n} \right)$ is a completely multiplicative function.
3. $\left(\dfrac{a}{mn} \right) = \left(\dfrac{a}{m}\right) \left(\dfrac{a}{n}\right).$
4. $\left(\dfrac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$, so it is $1$ if and only if $n \equiv 1$ mod $4$.
5. $\left(\dfrac{2}{n}\right)= (-1)^{\frac{n^2-1}{8}},$ so it is $1$ if and only if $n \equiv \pm 1$ mod $8$.
6. (Extension of the law of quadratic reciprocity:) If $m$ and $n$ are coprime positive odd integers, $$\left(\dfrac{m}{n}\right)\left(\dfrac{n}{m}\right)=(-1)^{\frac{m-1}{2} \frac{n-1}{2}}.$$

(1), (2), and (3) are immediate from the definition (and the corresponding properties of the Legendre symbol). The other three follow from the corresponding properties for the Legendre symbol, and then an induction on $n.$ To illustrate, here is a proof of (4) $($the proofs of (5) and (6) are similar$)$:

Induct on $n.$ When $n=1$ (base case), the result holds trivially. Now suppose the result holds for all positive odd integers less than $n.$ If $n$ is prime, the result is true by the corresponding theorem for the Legendre symbol. If $n$ is composite, write $n = xy,$ where $x$ and $y$ are positive odd integers less than $n.$ Then by the inductive hypothesis and property (2),

$$\begin{aligned} \left( \frac{-1}{xy} \right) &= \left( \frac{-1}{x} \right) \left( \frac{-1}{y} \right) \\ &= (-1)^{\frac{x-1}2}(-1)^{\frac{y-1}2} \\ &= (-1)^{\frac{x-1}2 + \frac{y-1}2} \end{aligned}$$

and now the result follows from the following lemma:

If $x$ and $y$ are odd, $\frac{x-1}2+ \frac{y-1}2 \equiv \frac{xy-1}2 \pmod 2.$

The proof of the lemma reduces to four cases based on whether $x$ and $y$ are $1$ or $3$ mod $4,$ and the statement can be verified easily in all four cases.

The lemma implies that

$$\left( \frac{-1}{xy} \right) = (-1)^{\frac{x-1}2 + \frac{y-1}2} = (-1)^{\frac{xy-1}2},$$

so the result holds for $n$ as well. Hence it holds for all $n$ by strong induction. $_\square$

The properties of the Jacobi symbol not only simplify computations of Jacobi symbols but those of Legendre symbols as well.

Is 1235 a quadratic residue mod the prime number 10007?

---

Use extended quadratic reciprocity repeatedly:

$$\begin{aligned} \left( \frac{1235}{10007} \right) = - \left( \frac{10007}{1235} \right) &= -\left( \frac{127}{1235} \right) \\ &= \left( \frac{1235}{127} \right) \\ &= \left( \frac{92}{127} \right) \\ &= \left( \frac{4}{127} \right) \left( \frac{23}{127} \right) \\ &= \left( \frac{23}{127} \right) \\ &= -\left( \frac{127}{23} \right) \\ &= -\left( \frac{12}{23} \right) \\ &= -\left( \frac{3}{23} \right) \\ &= \left( \frac{23}{3} \right) \\ &= \left( \frac23 \right) = -1, \end{aligned}$$

so the answer is no. Note that without using properties of the Jacobi symbol, the beginning part of the problem would have taken longer; if the top of the symbol was composite (as 1235 was), we would have had to factor it as a product of primes and then flipped each individual Legendre symbol using quadratic reciprocity. The properties of the Jacobi symbol allow us to avoid any factoring (except for factoring out powers of 2, which is always necessary). $_\square$

The Legendre symbol satisfies Euler's criterion:

$$\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}2} \pmod p$$

for $a$ coprime to $p.$ This is no longer true in general for the Jacobi symbol.

We have $\left( \frac{2}{35} \right) = -1,$ but $2^{17} \equiv -3 \pmod{35}.$

So this gives a criterion for primality: if there is an integer $a$ coprime to $n$ such that $\left( \dfrac{a}{n} \right) \not\equiv a^{\frac{n-1}2} \pmod n$, then $n$ cannot be prime.

It is not hard to show that if $n$ is composite, then at least half the positive $a$ less than $n$ that are coprime to $n$ satisfy this condition. Choosing random values of $a$ $k$ times leads to a probability of $\frac1{2^k}$ that none of the random values are witnesses to the compositeness of $n$ in this way. This probabilistic primality test is called the Solovay-Strassen primality test, and is quite efficient in practice. One interesting feature of the test is that it can be used to prove that numbers are composite without explicitly determining a nontrivial factor.

Show that $679$ is composite using the Solovay-Strassen primality test.

---

Suppose we randomly choose $a=62.$ It turns out that $\left( \frac{62}{679} \right) = -1$ and $62^{339} \equiv -1 \pmod{679}.$ This random choice leaves the outcome of the test inconclusive. Next suppose we randomly choose $a=2.$ In this case, $\left( \frac2{679} \right) = 1$ but $2^{339} \equiv 8 \pmod{679},$ so this immediately shows that $679$ is composite. $_\square$