Examples of Computing Jacobi Symbols

Recall from the Jacobi Symbols page that if $P, Q \in \mathbb{Z}$ and $Q$ has prime power factorization $Q = q_1^{e_1}q_2^{e_2}...q_k^{e_k}$ then the Jacobi symbol of $P$ over $Q$ is defined to be:

(1)

\begin{align} \quad \left ( \frac{P}{Q} \right ) = \left ( \frac{P}{q_1} \right )^{e_1} \left ( \frac{P}{q_2} \right )^{e_2} ... \left ( \frac{P}{q_k} \right )^{e_k} \end{align}

where the terms in the product on the right are Legendre symbols. We proved some basic properties of Jacobi symbols, which are summarized below:

• 1. $\left ( \frac{PP'}{Q} \right ) = \left ( \frac{P}{Q} \right ) \left ( \frac{P'}{Q} \right )$.

• 2. $\left ( \frac{P}{QQ'} \right ) = \left ( \frac{P}{Q} \right ) \left ( \frac{P}{Q'} \right )$.

• 3. If $P \equiv P' \pmod Q$ then $\left ( \frac{P}{Q} \right ) = \left ( \frac{P'}{Q} \right )$.

We also noted the following very important result:

If $\left ( \frac{P}{Q} \right ) = -1$ then $x^2 \equiv P \pmod Q$ has no solutions, just like with Legendre symbols. However, if $\left ( \frac{P}{Q} \right ) = 1$ then NOTHING can be determined!

Example 1

Compute the Jacobi symbol $\left ( \frac{5}{12} \right )$. Does $x^2 \equiv 5 \pmod {12}$ have any solutions?

We have that:

(2)

\begin{align} \quad \left ( \frac{5}{12} \right ) &= \left ( \frac{5}{2} \right )^2 \left ( \frac{5}{3} \right ) \\ &= \left ( \frac{1}{2} \right )^2 \left ( \frac{2}{3} \right ) \\ &= (-1)^2 \left ( \frac{2}{3} \right ) \\ &= \left ( \frac{2}{3} \right ) \end{align}

Since $3 \equiv 3 \pmod 8$ we have that $\left ( \frac{2}{3} \right ) = -1$. Hence $\left ( \frac{5}{12} \right ) = -1$. We conclude that $x^2 \equiv 5 \pmod {12}$ has no solutions.

Example 2

Compute the Jacobi symbol $\left ( \frac{16}{60} \right )$. Does $x^2 \equiv 16 \pmod {60}$ have any solutions?

We have that:

(3)

\begin{align} \quad \left ( \frac{16}{60} \right ) &= \left ( \frac{16}{2} \right )^2 \left ( \frac{16}{3} \right ) \left ( \frac{16}{5} \right ) \\ &= (1) \left ( \frac{1}{3} \right ) \left ( \frac{1}{5} \right ) \\ &= (1)(1)(1) \\ &= 1 \end{align}

We cannot conclude whether or not $x^2 \equiv 16 \pmod {60}$ has a solution by Jacobi symbols. However, it clearly does have a solution, namely $x = 4$.