2
$\begingroup$

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

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

The discriminante 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$
  • $\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$ – lab bhattacharjee Jun 11 '16 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$ – user5618793 Jun 11 '16 at 14:19
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$
  • $\begingroup$ So how can I find all solutions only for primes? $\endgroup$ – user5618793 Jun 11 '16 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$ – Ethan Bolker Jun 11 '16 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$

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.