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

$\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 ?

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$.
• but do you know how to show all quadratic residues $\mod15$ without wolframalpha ? – inequal Mar 15 '15 at 14:52