3
$\begingroup$

the question is: find all primes p that satisfy the equation:

x^2-2*x-5 = 0 (mod p)  

The discriminant is 24, and I know that the equation mod p has a solution if and only if 24 is a quadratic residue mod p.
I've used Legendre symbol and found that the solutions are:
p = +-1, +-5 (mod 24) [p=1,5,19,23 mod 24], and p=2,3.
However, something doesn't seem right, because for p=1 mod 24, 25 is not a prime!

When I've used Legendre symbol, I saw that (24/p) = (2/p) * (3/p), and found all cases when both 2 and 3 are quadratic residues mod p, and all cases in which both 2 and 3 are not quadratic residues mod p.
Maybe I missed something that the law of quadratic reciprocity requires? [I mean, I know that 2 is a quadratic residue mod p iff p = +-1 (8), and found (using the law of quadratic reciprocity) that 3 is a quadratic residue mod p iff p = +- 1 (12)].

Thanks

$\endgroup$
3
  • $\begingroup$ So, we need $$\left(\dfrac2p\right)=\left(\dfrac3p\right)=1$$ $$\left(\dfrac2p\right)=\left(\dfrac3p\right)=-1$$ Consider $p\pmod{\text{lcm}(12,8)}$ which are $\pm1,\pm5,\pm7,\pm11$ $\endgroup$ Jun 11, 2016 at 14:14
  • $\begingroup$ That's exactly what I've written above.... 25 isn't a prime, so +1 is not correct. How do I restrict the solutions only for primes? $\endgroup$ Jun 11, 2016 at 14:19
  • $\begingroup$ Your solution is correct: the primes for which $x^2-2x-5=0$ has solutions, are the primes that are in $S=\{s\equiv\pm1,\pm5\pmod{24}\}$. That means the equation has solutions for each prime $p\in S$, not that every member of $S$ is prime. $\endgroup$
    – robjohn
    Nov 12, 2020 at 9:07

2 Answers 2

1
$\begingroup$

You've proved that

If $p$ is prime then that equation has a solution if and only if (something about $p$ mod $24$).

But that says nothing about composite numbers that might happen to satisfy the congruence relation. This is not a problem:

However, something doesn't seem right, because for p=1 mod 24, 25 is not a prime!

$\endgroup$
2
  • $\begingroup$ So how can I find all solutions only for primes? $\endgroup$ Jun 11, 2016 at 14:19
  • $\begingroup$ You have found all the correct primes (if you didn't make a mistake - I haven't checked the work, only your logic). $\endgroup$ Jun 11, 2016 at 14:20
1
$\begingroup$

There are trivially solutions if $p=2$ or $p=3$ ($x=1$). So suppose $p>3$.

As $24=2^2\cdot 6$, $\,24$ is a quadratic residue mod $p$ if and only if $6$ is. Now $\newcommand\legendre[2]{\biggl(\dfrac#1#2\biggr)}$ $$\legendre6p=\legendre2p\legendre3p=(-1)^{\textstyle\frac{p^2-1}8}\legendre3p.$$ On the other hand, by the law of quadratic reciprocity $$\legendre 3p\legendre p3=(-1)^{\textstyle\frac{p-1}2}.$$

If $p\equiv 1$ or $-1\mod 8$, $\legendre2p=1$, so we must have $\legendre3p=1$, which is equivalent to

  • $\legendre p3=1\iff p\equiv 1\mod 3\; $ in the first case,
  • $\legendre p3=-1\iff p\equiv -1\mod 3\; $ in the second case.

If $p\equiv 3$ or $-3\mod 8$, $\legendre2p=-1$, so we must have $\legendre3p=-1$ as well, which is equivalent to

  • $\legendre p3=1\iff p\equiv 1\mod 3\; $ in the first case,

  • $\legendre p3=-1\iff p\equiv -1\mod 3\; $ in the second case.

So $p$ has to satisfy one of the set congruences: $$\begin{cases} p\equiv 1\mod8\\p\equiv1\mod 3 \end{cases}\qquad \begin{cases} p\equiv 3\mod8\\p\equiv1\mod 3 \end{cases}\qquad \begin{cases}p\equiv 1\mod8\\p\equiv1\mod 3\end{cases}, \qquad \begin{cases} p\equiv -3\mod8\\p\equiv-1\mod 3 \end{cases}$$ which have as solutions, respectively: $$1,\enspace -5,\enspace 7,\enspace 5\mod 24.$$

$\endgroup$
1
  • $\begingroup$ This is not right. The OP had the correct solutions, primes that are $\pm1,\pm5\pmod{24}$. Note that $\left(\frac6{31}\right)=-1$. However, $31\equiv7\pmod{24}$; so, according to your answer, $p=31$ should allow a solution. $\endgroup$
    – robjohn
    Nov 12, 2020 at 9:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .