# Jacobi symbol of quadratic residues

In my textbook there's the following definition:

Let $n$ be an odd number and $n = \prod_{i=1}^s q_i^{r_i}$ its prime factorization. Then the Jacobi symbol is defined as \begin{equation*} \left( \frac{a}{n} \right) = \prod_{i=1}^s\left( \frac{a}{q_i} \right)^{r_i} \, . \end{equation*} If $a$ is a quadratic residue modulo $n$, then the Jacobi symbol is $1$. Yet the reverse doesn't necessarily hold.

The symbol on the right side of the equation is the Legendre symbol (confusingly the symbol is "recycled" for the Jacobi symbol).

There is no explanation given whatsoever why this:

If $a$ is a quadratic residue modulo $n$, then the Jacobi symbol is $1$.

is true. Is it trivial and I don't see it? Ok, it seems to follow from the fact that the projection $\phi\colon \mathbb{Z}/n\mathbb{Z} \rightarrow \prod_{i=1}^s (\mathbb{Z}/q_i\mathbb{Z})^{r_i}$ is a ring homomorphism, right?

Ok, and now a counterexample for the assertion:

Yet the reverse doesn't necessarily hold.

Quadratic residues modulo $15$ are $$0, 1, 4, 6, 9, 10$$ but $$\left( \frac{2}{15} \right) = \left( \frac{2}{5} \right) \left( \frac{2}{3} \right) = (-1)\cdot(-1) = 1\,.$$ Am I right here?

• Isn’t the local factor defined to be zero when $q_i|a$? Commented Feb 25, 2015 at 4:59
• @Lubin: you're right. Too bad. So $\left(\frac{9}{15}\right) = 0$, but of course $x^2 \equiv 9 \bmod{15}$ has a solution. So they should have included "if $\gcd(a, n) = 1$". Commented Feb 26, 2015 at 20:57

By the Chinese remainder theorem, $a$ is a QR $\bmod n$ iff $a$ is a QR $\bmod p^k$ for all prime powers $p^k$ dividing $n$. In particular, if $a$ is a QR $\bmod n$, then $a$ is a QR $\bmod p$ for all primes $p$ dividing $n$. Is it clear now?
And your counterexample is fine. The point is that if $n$ is a product of distinct primes then the Jacobi symbol only tells you the parity of the number of prime factors $p$ of $n$ such that $\left( \frac{a}{p} \right) = 1$.
• Thanks. Isn't it "overkill" to use the CRT? Isn't it enough to know that $\phi\colon \mathbb{Z}/n \mathbb{Z} \rightarrow \mathbb{Z}/q_i \mathbb{Z}$ is a ring homomorphism? So if $x^2 = a$ is solvable in $\mathbb{Z}/n \mathbb{Z}$ the equation $y^2 = \phi(a)$ must solvable in $\mathbb{Z}/q_i\mathbb{Z}$ because $\phi(x^2) = \phi(a) \Rightarrow \phi(x)^2 = \phi(a)$, which means $y^2 \equiv a \bmod{q_i}$ is solvable, so the Legendre-symbol $\left(\frac{a}{q_i}\right) = 1$ for all $q_i$, $i = 1, \ldots, n$. And so their powers and the whole product must be one, too. Commented Feb 26, 2015 at 20:30