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$ ? 
 A: 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.
A: 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.
