# Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$

Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$

How would I go about doing this? I'm aware that if instead $y>1$ then I can write $y$ as a product of primes and use the law of quadratic reciprocity. However, this doesn't seem to be applicable if $y<-1$, as the Legendre/Jacobi symbol requires a positive number in the denominator, and since we do not know $q$, it seems (although I may be wrong) we cannot find a meaningful positive representative modulo $q$.

• You can add $q$ to $y$ as many times as needed to make it positive. Also, you can calculate the Legendre symbol value of $\frac{-1}{q}$. – Calvin Lin May 13 '13 at 1:14
• $\left( \frac{-1}{q} \right)=(-1)^\frac{q-1}{2}$ for odd $q$... You would need to study separately what happens when $q$ is even and prime ;) – N. S. May 13 '13 at 1:15

## 3 Answers

You can take out the $-1$ using the multiplicativity of the Legendre symbol, and use the first supplementary law: $$\left(\frac{-a}{q}\right)=\left(\frac{-1}{q}\right)\left(\frac{a}{q}\right)=(-1)^{(q-1)/2}\left(\frac{a}{q}\right)$$

• Gosh, I feel silly! Thank you! – Damien May 13 '13 at 1:33

There are $\frac{p-1}{2}$ quadratic residues between $1$ and $p-1$. Let $x$ be any of these, and let $y=x-17p$. Since $x$ is a quadratic residue of $p$, so is $y$.

Yet another easy problem: For some integer $$p$$, pick any integer $$x$$ and compute $$a=x^2\pmod p$$. $$-p+a$$ is a negative number that is a quadratic residue $$\pmod p$$. In fact, $$pk+a$$ is a quadratic residue that is a negative number as long as $$k$$ is negative.