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!

  • 1
    $\begingroup$ Use the law of quadratic reciprocity. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Apr 28 '18 at 22:07
  • $\begingroup$ @GNUSupporter I've looked into it, but I'm not sure how to use it properly here.. $\endgroup$ – Collapse Apr 28 '18 at 22:08
  • $\begingroup$ Use it together with the two supplements $\frac{-1}{p})$ and $(\frac{2}{p})$ to reduce large numbers to smaller numbers. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Apr 28 '18 at 22:10
  • $\begingroup$ @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. $\endgroup$ – Collapse Apr 29 '18 at 12:02

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

  • $\begingroup$ 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}$. $\endgroup$ – 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.

  • $\begingroup$ 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$? $\endgroup$ – Collapse Apr 29 '18 at 12:00
  • $\begingroup$ 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. $\endgroup$ – dyf Apr 29 '18 at 18:28

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.