3
$\begingroup$

When $p$ is not $11$ and $p$ is an odd prime, compute the Legendre symbol $\left(\dfrac{-11}{p}\right)$.

What I have done is that $\left(\dfrac{-11}{p}\right) = \left(\dfrac{-1}{p}\right)\left(\dfrac{11}{p}\right)=\left(\dfrac{p}{11}\right)$ by reciprocity. From this, I computed all the possible cases one by one (ex: $p$ is congruent with $1,2,3,4,5,6,7,8,9,10 \pmod{11}$).

But is there a more efficient way?

$\endgroup$
1
  • $\begingroup$ It looks like you used basically all you could with the info you were given, up and including QR which made the problem simpler than at the beginning. +1 $\endgroup$
    – DonAntonio
    May 30, 2016 at 11:51

1 Answer 1

3
$\begingroup$

You know that there are $5$ quadratic residues modulo $11$. (In general, there is $\frac{p-1}2$ quadratic residues and $\frac{p-1}2$ quadratic non-residues modulo a prime $p$.)

  • You can simply try $1^2=1$, $2^2=4$, $3^2=9$, $4^2\equiv5$ and $5^2\equiv3$. So you know that $1$, $3$, $4$, $5$ and $9$ are residues, the remaining ones are not. (This does not seem as a too much work for me.)
  • Or you can start with the three "obvious ones", i.e., $1$, $4$, $9$. Modulo $11$ we have $9=-2$. We get that $-2\cdot4=-8\equiv 3$ is a quadratic residue (product of two residues). So is $-2\cdot3=-6\equiv5$. So we get $1$, $4$, $9$, $3$ and $5$, which is a complete list. (In fact, this looks more complicated to me.)

In short, once you have $5$ quadratic residues, you do not have to continue.

$\endgroup$
1
  • $\begingroup$ To be honest, I was not entirely sure what you meant by the phrase "I computed all the possible cases one by one" in your question. So it is quite possible that I am posting as an answer exactly what you did. $\endgroup$ May 30, 2016 at 13:51

You must log in to answer this question.

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