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

Question

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!

Answer 1

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}$.

Answer 2

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.