# Find primes $p$, for which the $x^2 \equiv 7 \pmod{p}$ has a solution

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$ ?

• Use quadratic repicprocity law. – 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\}$.
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.$$
• Is there anything to $p\equiv 3^k \bmod 28$? – Oscar Lanzi May 27 '18 at 14:05