# Legendre Symbol - Find Prime $p$ Which Divides A Polynomial

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?

• 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. – anon May 30 '13 at 21:37
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?
• @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. – Warren Moore May 31 '13 at 7:46