# Find all primes $p > 11$ such that $11$ is a quadratic residue $\pmod p$.

Find all primes $p > 11$ such that $11$ is a quadratic residue $\pmod p$. (The answer should be in terms of congruence conditions mod a certain number.)

I believe that we need to find all primes $p > 11$ such that $\left( \frac{11}{p} \right) = 1$.
or $\left( \frac{11}{p} \right) = (-1)^{(p-1)/2}\left( \frac{p}{11} \right)$ by the reciprocity law.

How do I proceed from this? Any help is appreciated.

$$\left(\frac{11}{p}\right) = (-1)^{(p-1)/2} \left(\frac{p}{11}\right)$$

We now need to work with two cases:

• $p \equiv 1 \pmod{4}$

This means that:

$$\left(\frac{11}{p}\right) = \left(\frac{p}{11}\right)$$

The quadratic residues modulo $11$ are $1, 3, 4, 5$ and $9$.

• $p \equiv 3 \pmod{4}$

This means that:

$$\left(\frac{11}{p}\right) = -\left(\frac{p}{11}\right)$$

The quadratic non-residues modulo $11$ are $2, 6, 7, 8$ and $10$.

With this information, you should be able to finish the problem yourself (hint: use the Chinese Remainder Theorem).

• Would the Chinese remainder theorem, say that there's a unique number $\pmod {4*{11}}$ satisfying the congruences: $x = 1,3,4,5,9 \pmod {11}$ and $x = 1 \pmod 4$? do we need to solve this system of $6$ congruences? – mike russel Apr 2 '15 at 0:13
• @mikerussel, take them two at a time. You want $x \equiv 1 \pmod{11}$ and $x \equiv 1 \pmod{4}$, then you want $x \equiv 3 \pmod{11}$ and (still) $x \equiv 1 \pmod{4}$, then you want $x \equiv 4 \pmod{11}$ and $x\equiv 1 \pmod{4}$, etc. etc. This will give you a bunch of congruences, and if $p$ satisfies any of them it will be a quadratic residue. – George V. Williams Apr 2 '15 at 0:15
• Alright, Thank a lot! – mike russel Apr 2 '15 at 0:16

Treat the two factors $(-1)^{(p-1)/2}$ and $\left(\frac p{11}\right)$ separately. The first is $1$ if $p$ is 1 mod 4 and it's $-1$ if $p$ is 3 mod 4. The second is $1$ if $p$ is 1,3,4,5, or 9 mod 11 and $-1$ otherwise. Combining the two, you can determine $\left(\frac{11}p\right)$ in terms of the congruence class of $p$ mod $44$.