How do I go about solving $x^2\equiv 116 \mod 587$ for $x$?

I know that 587 is prime. How would I get started?

I know $116= 2^2\cdot 29$

I think if I can solve $116^{147}\mod 587$, then I will have answer?

  • $\begingroup$ You need to find the (square) roots of $b^e\mod m$. That is, those numbers whose square is congruent to $b^e\mod m$. $\endgroup$ – Justin Benfield Apr 13 '16 at 23:01
  • $\begingroup$ This is relevant: johndcook.com/blog/quadratic_congruences $\endgroup$ – Justin Benfield Apr 13 '16 at 23:16
  • 1
    $\begingroup$ Your exponential version is correct. Now we need to calculate, using modular exponentiation, the binary method or a variant. A little unpleasant, to be sure, but doable with a cheap calculator. $\endgroup$ – André Nicolas Apr 14 '16 at 0:39
  • $\begingroup$ You are correct: $\pm 116^{147} \bmod 587$ are all the solutions of $x^2\equiv 116\pmod{587}$, and it's simple to prove using Euler's Criterion and Quadratic Reciprocity. You can express the answer in this closed exponential form because $587$ is a prime of the form $4k+3$. It would be more difficult if it were a prime of the form $8k+1$. See this paper for how to solve $x^2\equiv a\pmod p$ with $p$ prime in general. $\endgroup$ – user236182 Apr 14 '16 at 1:21
  • $\begingroup$ I got 65, if that's correct? $\endgroup$ – Jeanie Apr 14 '16 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.