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

  • $\begingroup$ but do you know how to show all quadratic residues $\mod15$ without wolframalpha ? $\endgroup$ – inequal Mar 15 '15 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.