I want to determine for which primes $p$ the following congruence has a solution.

$$x^2 \equiv 7 \pmod{p}.$$

I have thought the following.

We are looking for the primes $p$ for which the Legendre symbol $\left( \frac{7}{p}\right)=1$. Then $(7,p)=1$.

If $p$ is odd, we have from Euler's theorem that

$$\left( \frac{7}{p}\right)=7^{\frac{p-1}{2}} \pmod{p}$$

So we would want that $7^{\frac{p-1}{2}} \pmod{p}=1$.

But does this help in order to find the desired primes $p$ ?

  • 2
    $\begingroup$ Use quadratic repicprocity law. $\endgroup$ – Watson May 27 '18 at 10:29

It's a little longer. From law of quadratic reciprocity, we have $$\biggl(\frac7p\biggr)=\biggl(\frac p7\biggr)(-1)^{\tfrac{p-1}2},$$ \begin{align}&\text{On the other hand, }&&\begin{cases}(-1)^{\tfrac{p-1}2}=1&\text{if }\;p\equiv 1\mod 4,\\(-1)^{\tfrac{p-1}2}=-1&\text{if }\;p\equiv 3\;(\text{or }-1)\mod 4. \end{cases}&&\hspace{10em}\end{align} Also the list of non-zero squares mod. $7$ is$\enspace\bigl\{1,\,2,\,4\bigr\}$.

So we have to solve the systems of congruences: \begin{align} &\begin{cases}p\equiv 1\mod4,\\p\equiv 1,\,2,\,4\mod 7, \end{cases} & &\qquad\begin{cases}p\equiv -1\mod4,\\p\equiv 3,\,5,\,6\mod 7, \end{cases} \end{align} To solve these systems, we use the explicit formula for the inverse isomorphism of the abstract form of the Chinese remainder theorem.

More precisely, start from a Bézout's relation between $4$ and $7$, e.g. $\;4\cdot 4-1\cdot 7=1$. Then $$\begin{cases}p\equiv a\mod4,\\p\equiv b\mod 7 \end{cases}\iff p\equiv 4\cdot 4\, b- 7a \mod 28$$ In all, you should find, if I'm not mistaken: $$p\equiv \pm 1,\pm3,\pm 9\mod 28. $$


As @OscarLanzi observed, this list can be simplified to $$x^2 \equiv 7 \;\text{ has a solution mod. }p \iff p \equiv 3^k \mod 28 \;\text{ for some }k.$$ This is because $3$ has order $6\bmod 28$. Indeed the successive power of $3$ mod. $28$ are: $$ 1,\;3,\;9,\;3^3\equiv -1,\;3^4\equiv -3,\;3^5\equiv -9, \;3^6\equiv -27\equiv 1 \mod 28.$$

  • $\begingroup$ Is there anything to $p\equiv 3^k \bmod 28$? $\endgroup$ – Oscar Lanzi May 27 '18 at 14:05
  • 1
    $\begingroup$ @OscarLanzi: Yes, there is. I've added you remark to my answer (with due credits, of course!). $\endgroup$ – Bernard May 27 '18 at 14:25

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.