1
$\begingroup$

The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that: $$ x(x+1)\equiv 1 \pmod{p} $$ The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.

$\endgroup$
  • 2
    $\begingroup$ Have you tried completing the square? $\endgroup$ – JavaMan Dec 9 '18 at 23:57
  • 1
    $\begingroup$ Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration. $\endgroup$ – Batominovski Dec 10 '18 at 0:03
2
$\begingroup$

Completing the square is the most obvious approach. Starting from

$$x^2+x-1\equiv 0\pmod p$$

we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$: $$ 4x^2+4x-4\equiv 0\pmod p\iff (2x+1)^2\equiv 5\pmod p.$$ Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)

$\endgroup$
  • $\begingroup$ Oh yeah that makes sense. Thank you for the help! $\endgroup$ – joseph Dec 10 '18 at 1:51
  • 1
    $\begingroup$ Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $p\equiv +/-1 \pmod{5}$ or $p=5$. $\endgroup$ – joseph Dec 10 '18 at 2:57
1
$\begingroup$

For odd $p$, multiply through by $4$ to get

$$4x^2+4x+1 \equiv 5 \pmod{p}.$$

Enough?

$\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.