3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint $\ 5\equiv 5+11\pmod{11}\ \ $ $\endgroup$ – Bill Dubuque Jul 15 '17 at 20:30
  • $\begingroup$ 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. $\endgroup$ – Anurag A Jul 15 '17 at 20:34
  • $\begingroup$ Try $x=\frac{1}{4} (-1)^n \left(11 (-1)^n (2 n-1)-5\right),\;\forall n\in\mathbb{Z}$ $\endgroup$ – Raffaele Jul 16 '17 at 15:52
1
$\begingroup$

How about a slightly different approach:

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

$\endgroup$
0
$\begingroup$

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.

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