4
$\begingroup$

I need to find a general form of a prime number $p$ which divides the polynomial $x^2-6$, i.e. $p$ such that $x^2 - 6\equiv 0\text{ (mod }p)$. By Legendre symbol, I actually need to find a prime p such as $\left(\frac{6}{p}\right) = 1$.

I know that $\left(\frac{6}{p}\right) = \left(\frac{3}{p}\right)\left(\frac{2}{p}\right)$, so there are two options at the moment:

  1. Both $\left(\frac{3}{p}\right) = 1$ and $\left(\frac{2}{p}\right) = 1$.
  2. Both $\left(\frac{3}{p}\right) = -1$ and $\left(\frac{2}{p}\right) = -1$.

I'd like to find out how could I find a general form of a prime $p$ which answers the two terms above?

Thanks in advance

|cite|improve this question
$\endgroup$
  • $\begingroup$ I suspect en.wikipedia.org/w/… is the key $\endgroup$ – Ben Millwood May 30 '13 at 20:55
  • $\begingroup$ The polynomial $x^2-6$ is never $0$ mod any $p$. Surely you mean $\exists x:x^2\equiv 6\bmod p$. What you do is you replace the legendre conditions $\left(2\,,\,3\over p\right)=\pm1$ with congruences via QR, then combine congruences via SZ aka CRT. $\endgroup$ – anon May 30 '13 at 21:37
2
$\begingroup$

The second supplement to the law of quadratic reciprocity gives you that $\left(\frac{2}{p}\right)=1$ if $p\equiv\pm 1\text{ (mod }8)$, and $-1$ if $p\equiv\pm 3\text{ (mod }8)$. It can also be shown that $\left(\frac{3}{p}\right)=1$ if $p\equiv\pm 1\text{ (mod }12)$ using quadratic reciprocity. Can you go from here?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ First of all , thanks for the answer . I know that I can infer the information above using the law of quadratic reciprocity, the problem is what should I do from now on to get the final answer. I'll be greatful if you could help me get to the point $\endgroup$ – itamar May 31 '13 at 6:45
  • 1
    $\begingroup$ @itamar Well if $p\equiv 1\text{ (mod }8)$ and $p\equiv 1\text{ (mod }12)$, then you know you can write $p=8k+1$. Substitute this into the second congruence, and you get that $8k+1\equiv 1\text{ (mod }12)$, hence $8k\equiv 0\text{ (mod }12)$. Solving gives that $k\equiv 0\text{ (mod }3)$, so $k=3j$, and $p=8(3j)+1=24j+1$. So if $p\equiv 1\text{ (mod }24)$, then the result is true. Now you just need to go through all the other cases, solving the congruences, until you've solved them all. $\endgroup$ – Warren Moore May 31 '13 at 7:46

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.