1
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Isn’t the local factor defined to be zero when $q_i|a$? $\endgroup$
    – Lubin
    Commented Feb 25, 2015 at 4:59
  • $\begingroup$ @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$". $\endgroup$
    – Ystar
    Commented Feb 26, 2015 at 20:57

1 Answer 1

Reset to default
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Ystar
    Commented Feb 26, 2015 at 20:30
  • 2
    $\begingroup$ @aRaRa: yes, it's overkill to use the CRT to get the implication you want, but the point of using the CRT is to see exactly why the reverse implication fails. $\endgroup$
    – Qiaochu Yuan
    Commented Feb 26, 2015 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .