2
$\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
  • 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, 2013 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, 2013 at 1:15

3 Answers 3

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$
1
  • $\begingroup$ Gosh, I feel silly! Thank you! $\endgroup$
    – Damien
    May 13, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .