2
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – TonyK Dec 15 '13 at 19:13
  • $\begingroup$ Yes, that is more direct. $\endgroup$ – André Nicolas Dec 15 '13 at 19:14
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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!

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