# Determine $p$ such that $x^2 \equiv a \pmod{p}$ using Legendre symbols(for specific values of $a$)

Determine $p$ such that $x^2 \equiv a \pmod{p}$ has a solution.(where $p$ is a prime)

How would you approach this for "bigger" numbers, if you would want to solve this using Legendre symbols and their properties.

E.g. if $a = -2$ you could break the case into $(\frac{-1}{p})(\frac{2}{p})=1$ and solve by applying explicit terms for ($\frac{1}{p}),(\frac{-1}{p})$and$(\frac{2}{p})$.(Legendre symbols from number theory).

How would you approach this if $a$ is for example $6$.

Then you would need to solve $(\frac{3}{p})(\frac{2}{p})=1$ which yields two options, either they are both $1$ or $-1$ but how would I reach anything useful from $(\frac{3}{p})=1$

EDIT : especially how to deal with even bigger ones, such as $(\frac{7}{p})$. How do I even know I covered all the options?

Thanks in advance!

• Use the law of quadratic reciprocity. – GNUSupporter 8964民主女神 地下教會 Apr 28 '18 at 22:07
• @GNUSupporter I've looked into it, but I'm not sure how to use it properly here.. – Collapse Apr 28 '18 at 22:08
• Use it together with the two supplements $\frac{-1}{p})$ and $(\frac{2}{p})$ to reduce large numbers to smaller numbers. – GNUSupporter 8964民主女神 地下教會 Apr 28 '18 at 22:10
• @GNUSupporter you just repeated what I asked. Thanks a lot for your time but that is exactly what I said I don't know how to do. – Collapse Apr 29 '18 at 12:02

## 2 Answers

To solve $(\frac{3}{p})$ or any other $(\frac{p_1}{p})$ where $p_1\geq 3$ is prime, you should be familiar with Euler's criterion $\left({\frac {a}{p}}\right)\equiv a^{{(p-1)/2}}{\pmod p}$ and Quadratic reciprocity. Let me show you how to deal with $(\frac{3}{p})$ , same goes for the others.

Let's say $(\frac{3}{p})=1$. By the law of quadratic reciprocity we got $\left({\frac {3}{p}}\right)\left({\frac {p}{3}}\right)=(-1)^{{{\frac {p-1}{2}}{\frac {3-1}{2}}}}=(-1)^{\frac {p-1}{2}}$. $Case\ 1$

$(-1)^{\frac {p-1}{2}}=1$, then\begin{cases} (\frac{p}{3})=1 => Euler => p \equiv 1 \pmod{3}\\\\ p \equiv 1 \pmod{4}. \end{cases} $Case\ 2$

$(-1)^{\frac {p-1}{2}}=-1$, then\begin{cases} (\frac{p}{3})=-1 => Euler => p \equiv -1 \pmod{3}\\\\ p \equiv 3 \pmod{4}. \end{cases} For $(\frac{3}{p})=-1$ use the same strategy.

To solve for $p$ , use Chinese theorem remainder. $Case\ 1$: $p \equiv 1 \pmod{12}$

$Case\ 2$: $p \equiv 11 \pmod{12}$.

• For e.g. $(\frac{p}{7})=1$ you are getting $p^3 \equiv 1 \pmod{7}$ which leads to $p \equiv 1 \pmod{7}$, $p \equiv 2 \pmod{7}$,$p \equiv 4 \pmod{7}$. – Kenkar Apr 30 '18 at 9:41

I'll follow up on GNU Supporter's comment, with your given explicit example. If we have $(\frac{3}{p})=1$, then the law of quadratic reciprocity says

• if $p\equiv 1 \pmod{4}$, then $(\frac{p}{3})=1$, so $p \equiv 1\pmod{3}$ (a priori $p =3$ case is easy to deal with separately). Combining we have $p \equiv 1 \pmod{12}$.
• if $p \equiv 3\pmod{4}$, then $(\frac{p}{3}) = -1$, so $p \equiv 2 \pmod{3}$. Combining we have $p \equiv 11 \pmod{12}$.

You can deal with the other cases similarly.

• I'm not sure about bigger numbers. If you had $(\frac{7}{p})$ what would you know, for example, from $(\frac{p}{7}) = 1$. Would you have to test for all numbers $k =0,1,2,3,4,5,6,$ whether $(\frac{k}{7}) = 1$? – Collapse Apr 29 '18 at 12:00
• One can do that, but in general we look at the remainder of $p$ when divided by $7$, say $a$, then we have $(\frac{a}{7})$, then we can break up $a$ into smaller primes, then rinse and repeat the previous steps if necessary. – dyf Apr 29 '18 at 18:28