1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Calvin Lin May 13 '13 at 1:14
  • $\begingroup$ $\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 ;) $\endgroup$ – N. S. May 13 '13 at 1:15
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Gosh, I feel silly! Thank you! $\endgroup$ – Damien May 13 '13 at 1:33
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.