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$
  • $\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 '16 at 11:51
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$
  • $\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$ – Martin Sleziak May 30 '16 at 13:51

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.