Verifying that $2^{44}-1$ is divisible by $89$ As the title, I was asked to show that $2^{44}-1$ is divisible by $89$.
My first attempt is to change the expression into $(2^{22}-1)(2^{22}+1)$.
Then further simplified it into $(2^{11}-1)(2^{11}+1)(2^{22}+1)$, I used my calculator and was able to show that $2^{11}-1$ is divisible by $89$ but then I don't know how to show it with modular arithmetic. I do think that it is quite similar to the form where we can use the Fermat's little theorem. $(\sqrt{2})^{88}-1$. (Though I do understand Flt can only be applied to integer.)
Can someone tell me whether I can take square root in modular arithmetic as well? I am still pretty new to the modular arithmetic. Thank you very much.
 A: An idea:
$$2^5=32=-57\pmod{89}\;\;,\;\;2^6=64=-25\pmod{89}\implies$$
$$2^{11}=32(-25)=-800=1\pmod{89}$$
since $\;801=9\cdot 89\;$
A: You can use exponentiating by squaring:
Consider the following numbers mod $89$:
$2^1=2$
$2^2=4$
$4^2={(2^2)}^2=2^4=16$
${16}^2={(2^4)}^2=2^8=256\equiv 78 \pmod{89}$
$78^2={(2^8)}^2=2^{16}\equiv{(-11)}^2\equiv32\pmod{89}$
We have $2^{16}\equiv32=2^5$.So,$2^{16}\equiv2^5$ hence $2^{11}\equiv1\pmod{89}$.
We can easily see now that $2^{44}={(2^{11})}^4\equiv1^4\equiv1\pmod{89}$ .
I believe this is the shortest way.
By the way:You can take square roots with modular arithmetic if the exponents you are dealing with,are even numbers!
A: Hint: By Fermat's Theorem, we have $2^{88}\equiv 1\pmod{89}$.
So $(2^{44}-1)(2^{44}+1)\equiv 0 \pmod{89}$.
If we can show that $2^{44}+1\not\equiv 0\pmod{89}$ we will be finished. 
One way to do this is to use the fact that $2$ is a quadratic residue of $89$, since $89$ is of the shape $8k+1$.
Remark: Your direct computational approach is perfectly fine. However, it may be that you are expected to make use of "theory," as in the approach described above.  
