# Legendre symbol $(-11/p)$

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?

• 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 – DonAntonio May 30 '16 at 11:51

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.