# Solving $x^2\equiv b \mod p$ for $p$ prime

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?

• 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$. – Justin Benfield Apr 13 '16 at 23:01
• This is relevant: johndcook.com/blog/quadratic_congruences – Justin Benfield Apr 13 '16 at 23:16
• 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. – André Nicolas Apr 14 '16 at 0:39
• 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. – user236182 Apr 14 '16 at 1:21
• I got 65, if that's correct? – Jeanie Apr 14 '16 at 11:47