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.


By quadratic reciprocity:

$$ \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).

  • $\begingroup$ 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? $\endgroup$ – mike russel Apr 2 '15 at 0:13
  • $\begingroup$ @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. $\endgroup$ – George V. Williams Apr 2 '15 at 0:15
  • $\begingroup$ Alright, Thank a lot! $\endgroup$ – 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$.


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.