Jacobi Symbols

We have already defined Legendre Symbols. We now extend this concept with fewer restrictions.

Definition: Let $P, Q \in \mathbb{Z}$ and let $Q = q_1^{e_1}q_2^{e_2}...q_k^{e_k}$ be the prime power factorization of $Q$. Then the Jacobi Symbol of $P$ and $Q$ is defined as $\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}$, where the product on the righthand side consists of Legendre symbols.

We now state some properties of Jacobi symbols.

Proposition 1: Let $P, P', Q, Q' \in \mathbb{Z}$. Then: 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 )$. 4. $\left ( \frac{P^2}{Q} \right ) = 1$ and if $(P, Q) = 1$ then $\left ( \frac{P}{Q^2} \right ) = 1$.

• Proof: Let $Q = q_1^{e_1}q_2^{e_2}...q_s^{e_s}$ and let $Q' = r_1^{f_1}r_2^{f_2}...r_t^{f_t}$.

• 1) We have by the multiplicity property of the Legendre symbol that:

(1)

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

• 2) Since $QQ' = q_1^{e_1}q_2^{e_2}...q_s^{e_s}r_1^{f_1}r_2^{f_2}...r_t^{f_t}$, by the definition of the Jacobi symbol:

(2)

\begin{align} \quad \left ( \frac{P}{QQ'} \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} \left ( \frac{P}{r_1} \right )^{f_1} \left ( \frac{P}{r_2} \right )^{f_2} ... \left ( \frac{P}{r_t} \right )^{f_t} \\ &= \left ( \frac{P}{Q} \right ) \left (\frac{P}{Q'} \right ) \end{align}

• 3) Suppose that $P \equiv P'$. Then $\left ( \frac{P}{q_i} \right ) \equiv \left ( \frac{P'}{q_i} \right)$ (as Legendre symbols) for each $1 \leq i \leq k$. Therefore:

(3)

\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} \\ &= \left ( \frac{P'}{q_1} \right )^{e_1} \left ( \frac{P'}{q_2} \right )^{e_2} ... \left ( \frac{P'}{q_k} \right )^{e_k} \\ &= \left ( \frac{P'}{Q} \right ) \end{align}

• 4) We have that $\left ( \frac{P^2}{q_i} \right ) = 1$ (as Legendre symbols) for each $1 \leq i \leq k$, and so:

(4)

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

Proposition 2: Let $P, Q \in \mathbb{Z}$. Then: 1) If $(P, Q) = 1$ and $Q$ is odd then $\left ( \frac{-1}{Q} \right ) = (-1)^{(Q - 1)/2}$. 2) $\left ( \frac{2}{Q} \right ) = (-1)^{(Q^2 - 1)/8}$. 3) If $P$ is odd then $\left ( \frac{P}{Q} \right ) \left ( \frac{Q}{P} \right ) = (-1)^{\frac{P-1}{2} \cdot \frac{Q - 1}{2}}$.

Proposition 3: Let $P, Q \in \mathbb{Z}$. If $\left ( \frac{P}{Q} \right ) = -1$ then $x^2 \equiv P \pmod Q$ has no solutions.

Note: The Jacobi symbol $\left ( \frac{P}{Q} \right ) = 1$ in general means NOTHING. The exception is when $Q$ is a prime in which case this Jacobi symbol implies that $x^2 \equiv P \pmod Q$ has a solution.