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

• It is a Mersenne number, you could try to see if that helps... – Lessa121 Dec 15 '13 at 18:47

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.

• Your chain of reasoning looks too long to me! If $2$ is a quadratic residue of $89$, so that $a^2=2 \mod 89$ for some $a$, then we have immediately that $2^{44} = a^{88} = 1 \mod 89$. We don't need to factorise anything. – TonyK Dec 15 '13 at 19:13
• Yes, that is more direct. – André Nicolas Dec 15 '13 at 19:14

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

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(mod89)$

$78^2={(2^8)}^2=2^{16}\equiv{(-11)}^2\equiv32(mod89)$
We have $2^{16}\equiv32=2^5$.So,$2^{16}\equiv2^5$ hence $2^{11}\equiv1mod89$.
We can easily see now that $2^{44}={(2^{11})}^4\equiv1^4\equiv1mod89$ .
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!