What primes $p$ give solutions to $x^{2} \equiv 7 ($mod $ p)$

Question

I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.

There are many different cases to consider but I do not know how to approach this problem.

Answer 1

Another hint:

An odd prime is congruent to $1$ or $3\mod 4$. Also, the non-zero squares modulo $7$ are $\;1,\,2$ and $4$. So

• If $p\equiv 1\mod 4$, $(-1)^{\tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $p\equiv 1,2,4$.
• If $p\equiv 3\mod 4$, $p$ has to be a non-square modulo $7$, i.e. $p\equiv3,5,6$

Now use the Chinese remainder theorem: $$\mathbf Z/4\mathbf Z\times \mathbf Z/7\mathbf Z\simeq\mathbf Z/28\mathbf Z$$ to find the images of the pairs $\{(1,1),\,(1,2),\,(1,4),\,(3,3),\,(3,5),\,(3,6)\}$ modulo $28$.

Answer 2

Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that

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

so we need

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

Now look at each residue for $p\bmod 7$ and determine what residue $p\bmod 4$ must be.

Answer 3

If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 \equiv 7 v^2 \pmod p \; . \; $$ Which, you know, means something.

     2    29    37    53   109   113   137   149   193   197
   233   277   281   317   337   373   389   401   421   449
   457   541   557   569   613   617   641   653   673   701
   709   757   809   821   877   953   977  1009  1033  1061

     3     7    19    31    47    59    83   103   131   139
   167   199   223   227   251   271   283   307   311   367
   383   419   439   467   479   503   523   563   587   607
   619   643   647   691   719   727   787   811   839   859
   887   971   983  1039  1063  1091  1123  1151  1223  1231