# Find square roots of $b$ mod $p$

Given $X^2 \equiv b \pmod p$ and $(p, b) = (11, 5)$, find all the all the square roots of $b \pmod p$.

So far, I've tried

$$b^{-1} = 9$$ $$9X^2 \equiv 45 \pmod{11} \equiv1 \pmod{11}$$ $$3x = \pm 1 \pmod{11}$$

But I'm not really sure where to go from here.

• Hint $\ 5\equiv 5+11\pmod{11}\ \$ – Bill Dubuque Jul 15 '17 at 20:30
• In your last step, you are basically solving $ax \equiv b \pmod{11}$ so multiply both sides with $3^{-1} \equiv 4$ to get $x \equiv \pm 4 \pmod{11}$. However you should be careful when you go from $9x^2 \equiv 1 \pmod{11}$ to $3x \equiv \pm 1 \pmod{11}$ because had it not been for mod $11$ (field) you wouldn't have this luxury. – Anurag A Jul 15 '17 at 20:34
• Try $x=\frac{1}{4} (-1)^n \left(11 (-1)^n (2 n-1)-5\right),\;\forall n\in\mathbb{Z}$ – Raffaele Jul 16 '17 at 15:52

$5^2\equiv 5^{12} \bmod 11$ from Fermat's Little Theorem
$5\equiv 5^6 \bmod 11$, if $5$ is to be a quadratic residue at all.
Then you have candidate square roots $5^3\equiv 4$ and its negative, which can be checked.
In general the candidate square roots of $b \bmod p$ determined this way are $\pm b^{\frac{p+1}{4}}$, if $p$ is a prime one less than a multiple of $4$. If the original radicand is not a quadratic residue, squaring the candidate roots gives the additive inverse of the radicand.
Compute the first squares $\pmod{11}$ and you will get that $4^2\equiv5\pmod{11}$. So, another square root of $5$ $\pmod{11}$ is $7(=-4)$. There are no other square roots, since we are dealing with a field and a quadratic equation here.