$\left(\frac{a}{n}\right)=1$ does not necessarily imply that, $a$ is a quadratic residue $\mod n$

Question

$\left(\frac{a}{n}\right)=1$ does not necessarily imply that, $a$ is a quadratic residue $\mod n$, where $\left(\frac{.}{.}\right)$ is the Jacobi symbol.

For example I know that $\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)^{\frac{3^2-1}{8}}(-1)^{\frac{5^2-1}{8}}=(-1)^1(-1)^3=1$

but $x^2\equiv2\mod 15$ has no integer solutions http://www.wolframalpha.com/input/?i=quadratic+residues+mod+15

Is there a generalization ?

$\textbf{EDIT}$: How can I find all quadratic residues $\mod 15 $ without wolframalpha ?

Answer 1

For $\left(\frac{a}{b}\right)$ to be a Legendre symbol, $b$ must be an odd prime. Legendre symbols do indeed determine whether $a$ is a quadratic residue mod $b$.

What you have with $b=15$ is a Jacobi symbol, which is a generalization of Legendre symbol. As you have discovered, if the Jacobi symbol is $1$, that tells us nothing, since it could be the product of an even number of $-1$'s. However if the Jacobi symbol is $-1$, then $a$ is a quadratic NONresidue mod $b$.

---

More info, as requested. Write $\left(\frac{a}{b}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots \left(\frac{a}{p_k}\right)$ where $b=p_1p_2\cdots p_k$ is a factorization into primes. If any of the Legendre symbols are $-1$, then $a$ is a nonresidue mod $b$. If all of the Legendre symbols are $1$, then $a$ is a residue mod $b$.

Answer 2

For the second part of your question which remains unanswered, one can find all the quadratic residues $\pmod n$ by considering all numbers up to $n$ modulo $n$, squaring all of them and considering the residues $\pmod n$. Notice that any other numbers, for example $n+2$, would have the same quadratic residue as the number reduced $\pmod n$, in this example $2$, would, hence this list would cover all of the residues (In the taken example, $(n+2)^2 \equiv 2^2 \equiv 4 \pmod n$, provided $4<n$ or it would be reduced further). Notice that we can write the last $\lfloor\frac{n}{2}\rfloor$ numbers in our set as negative counterparts of previous numbers which would have the same quadratic residue $\pmod n$. This means that we only need to check upto $\lceil\frac{n}{2}\rceil$ and would cover all residues.

To make this clearer I will do this procedure for $7$.

$\begin{array}{| c | c | c |}\hline \text{n} & n^2 \pmod 7 \\ \hline 1 & 1\\ \hline 2 & 4 \\ \hline 3 & 2 \\ \hline 4 & 2 \\ \hline \end{array}$

The above table implies that the only quadratic residues$\pmod 7$ are $1,2,4$. One can repeat this process for $15$ to get that the quadratic residues are $1,4,6,9,10$. Notice that this does not include $2$, hence $2$ is a quadratic nonresidue.

Answer 3

For example, for $N=p_1...p_n$ a product of distinct odd primes, an integer $b$ is a square mod $N$ if and only if it is a square mod $p_i$ for all the $p_i$. Quadratic reciprocity can be used to compute whether $b$ is a square mod $p_i$, using the extended Jacobi-symbol version... whose intermediate steps do not care whether it is determining whether something is a square or not. That is, the (relatively fast) algorithm using quadratic reciprocity and the (extended...) Jacobi symbol is absolutely necessary for the basic assertions of quadratic reciprocity to be computationally useful. :)

Also, by Hensel's lemma, for powers $p^e$ of an odd prime, an integer $b$ is a square if and only if it's a square mod $p$.

And so on. The thing that took years to percolate into my own head was the utility of the Jacobi symbol (and its extended reciprocity law) to determine whether something is a square mod $p$... even though the Jacobi symbol does not directly address this! :)