Compute sqrt(5) in Z_11 with Fermat's little theorem
I am trying to solve this.
If I am correct, applying Fermat's little theorem here gives:
$\sqrt{5}^{10} \equiv 1 \pmod{11}$
$\sqrt{5}^{10} = 5^5 \equiv 1 \pmod{11}$
$5^{2} \equiv 3 \pmod{11}$
$5^{3} \equiv 5*5^2 \equiv 3*5 \equiv 4 \pmod{11}$
$5^{5} \equiv 5^2*5^3 \equiv 3*4 \equiv 1 \pmod{11}$
but I have no idea how to use the fact that $11 \equiv 3 \pmod{4}$
and also, since $Z_{11}^*$ = {1,2,3,4,5,6,7,8,9,10} is not the $\sqrt(5)$ in $Z_{11}^*$ the same as in $Z$ ?
$\endgroup$ 32 Answers
$\begingroup$You've thrashed around a bit, but you've managed to close in on a solution.
Since $5^5 \equiv 1 \bmod 11$ as you verified, also $5^6 \equiv 5 \bmod 11$.
So:
$5^3$ is a square root of $5$ modulo $11$.
However this discrete square root of $5$ mod $11$ is not "the same" as a square root in the integers $\mathbb{Z}$. Not sure how you meant that last remark.
This is a particular case where, given a quadratic residue $n$ mod $p$, when prime $p$ is congruent to $3$ mod $4$, the modular square roots of $n$ mod $p$ can be explicitly computed or expressed as:
$$ \pm n^{\frac{p+1}{4}} $$
This may well have been discussed in your text or other study materials. In any case it is mentioned as the first step of the Tonelli-Shanks algorithm.
$\endgroup$ 3 $\begingroup$Some supplementary background to hardmath's answer.
Note that $\sqrt{5}$ does not exist in $\mathbb{Z}$.
The answer is "obviously" $4$. Indeed, $4^2 = 16 \equiv 5 \pmod{11}$. This would be entirely a sufficient answer. For toy questions like that, the answer is usually not very big, so you can just try the first few numbers which are $5 \pmod{11}$ and see if they're square.
There is an efficient algorithm for this kind of problem.
