# Find the primes $p$ such that the equation: $x^{2} + 6x + 15 = 0$ has a solution modulo $p$

I need to solve this question:

Find the primes $p$ such that the equation: $x^{2} + 6x + 15 = 0$ has a solution modulo $p$.

My approach was: I checked for $p = 2$ and there is no solution.

Now if $p \neq 2$ so the equation has a solution $\iff 6^{2} -4 \times 15 = -24$ is a square modulo $p$.

Now $-24$ is a square modulo $p \iff \left(\frac{-24}{p}\right) = 1$ (Legendre symbol) $\iff \left(\frac{-1}{p}\right) \left(\frac{2}{p}\right) \left(\frac{3}{p}\right) = 1.$

And now there are many cases to check and I'm not sure how to do it... For example - case 1:

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

$\left(\frac{-1}{p}\right) =1 \iff p \equiv 1 (4)$ ,
$\left(\frac{2}{p}\right) =1 \iff p \equiv 1, -1 (8)$ ,

$\left(\frac{3}{p}\right) = 1 \iff p \equiv 1, -1 (12)$

so how do I combine these results for case 1? and after that, do I really need now to check all the other cases - that 2 of the Legendre symbols are $(-1)$ and one is $1$ ?

• $x=1$ is a solution modulo $2$... – Henning Makholm Aug 3 '16 at 21:47
• @HenningMakholm right, my mistake – CnR Aug 3 '16 at 21:51
• You correctly saw that the answer depends on the residue class of $p$ modulo $4,8,$ and $12$. This suggests that it is natural to combine those conditions, and write the answer in terms of residue class of $p$ modulo the least common multiple $24$. Knowing the residue of $p$ mod $24$ also gives its residues modulo $4,8$ and $12$, so you can write down a nice table with $\phi(24)=8$ rows :-) – Jyrki Lahtonen Aug 3 '16 at 21:51
• Related: math.stackexchange.com/questions/2047575, and also generalizations math.stackexchange.com/questions/2233442, math.stackexchange.com/questions/378331 – Watson Feb 17 '18 at 22:08

## 2 Answers

Your approach is overall alright; an issue with $p=2$ was already mentioned in a comment, further note that you also should treat $p=3$ separately.

To combine the congruences in your specific case is not hard in an ad-hoc way.

You have that $p$ needs to be $1$ modulo $4$, thus it cannot be $-1$ modulo $8$ and also not $-1$ modulo $12$. So $p$ is $1$ modulo $4$ and modulo $8$ and modulo $12$, implying it is $1$ modulo their LCM that is $24$.

Then, indeed, I would consider the three other cases in an analogue way; the congruences might be somewhat harder to treat but not by much.

$x^2+6x+15 \equiv 0\pmod{p}\Rightarrow(x+3)^2+6\equiv0\pmod{p}\Rightarrow (x+3)^2\equiv-6\pmod{p}$.
In other words, $y^2\equiv -6\pmod{p}$ or to rephrase the argument, $\left(\frac{-6}{p}\right)=1$

• How do you decide for which $p$ it is true that $-6$ is a quadratic residue? Presumably by reducing it to the problem for $-1$, $2$, $3$, which is what OP did already. – quid Aug 4 '16 at 8:54