Prove that ## 89\mid (2^{44}-1) ## and ## 97\mid (2^{48}-1) ##

[Math100]

Homework Statement

Use the theory of congruences to verify that ## 89\mid (2^{44}-1) ## and ## 97\mid (2^{48}-1) ##.

Relevant Equations

None.

Proof:

First, consider ## 89\mid (2^{44}-1) ##.
Observe that
\begin{align*}
2^{44}-1&\equiv (2^{11})^{4}-1\pmod {89}\\
&\equiv [(1)^{4}-1]\pmod {89}\\
&\equiv (1-1)\pmod {89}\\
&\equiv 0\pmod {89}.\\
\end{align*}
Thus ## 89\mid (2^{44}-1) ##.
Next, consider ## 97\mid (2^{48}-1) ##.
Observe that
\begin{align*}
2^{48}-1&\equiv [(2^{6})^{8}-1]\pmod {97}\\
&\equiv [(-33)^{2}]^{4}-1\pmod {97}\\
&\equiv (22^{4}-1)\pmod {97}\\
&\equiv [(22^{2})^{2}-1]\pmod {97}\\
&\equiv [(-1)^{2}-1]\pmod {97}\\
&\equiv (1-1)\pmod {97}\\
&\equiv 0\pmod {97}.\\
\end{align*}
Thus ## 97\mid (2^{48}-1) ##.
Therefore, ## 89\mid (2^{44}-1) ## and ## 97\mid (2^{48}-1) ##.

 

[fresh_42]

Homework Statement:: Use the theory of congruences to verify that ## 89\mid (2^{44}-1) ## and ## 97\mid (2^{48}-1) ##.
Relevant Equations:: None.

Proof:

First, consider ## 89\mid (2^{44}-1) ##.
Observe that
\begin{align*}
2^{44}-1&\equiv (2^{11})^{4}-1\pmod {89}\\
&\equiv [(1)^{4}-1]\pmod {89}\\
&\equiv (1-1)\pmod {89}\\
&\equiv 0\pmod {89}.\\
\end{align*}
Thus ## 89\mid (2^{44}-1) ##.
Next, consider ## 97\mid (2^{48}-1) ##.
Observe that
\begin{align*}
2^{48}-1&\equiv [(2^{6})^{8}-1]\pmod {97}\\
&\equiv [(-33)^{2}]^{4}-1\pmod {97}\\
&\equiv (22^{4}-1)\pmod {97}\\
&\equiv [(22^{2})^{2}-1]\pmod {97}\\
&\equiv [(-1)^{2}-1]\pmod {97}\\
&\equiv (1-1)\pmod {97}\\
&\equiv 0\pmod {97}.\\
\end{align*}
Thus ## 97\mid (2^{48}-1) ##.
Therefore, ## 89\mid (2^{44}-1) ## and ## 97\mid (2^{48}-1) ##.

Correct.

But ##2^{11}\equiv 1\pmod{89}\, , \,33^2\equiv 22 \pmod{97}\, , \,22^2\equiv -1 \pmod{97}## isn't obvious. Maybe you should have added some steps there.

 

[Math100]

First, consider ## 89\mid (2^{44}-1) ##.
Then ## 2^{44}-1\equiv (2^{11})^{4}-1\pmod {89} ##.
Note that ## 2^{11}\equiv 1\pmod {89} ##.
Thus ## 2^{44}-1\equiv [(1)^{4}-1]\pmod {89}\equiv (1-1)\pmod {89}\equiv 0\pmod {89} ##.
Therefore, ## 89\mid (2^{44}-1) ##.
Next, consider ## 97\mid (2^{48}-1) ##.
Then ## 2^{48}-1\equiv [(2^{6})^{8}-1]\pmod {97} ##.
Note that ## 2^{6}\equiv -33\pmod {97}\implies (2^{6})^{8}\equiv (-33)^{8}\pmod {97} ##, ## 33^{2}\equiv 22\pmod {97} ## and ## 22^{2}\equiv -1\pmod {97} ##.
Thus
\begin{align*}
2^{48}-1&\equiv [(-33)^{2}]^{4}-1\pmod {97}\\
&\equiv (22^{4}-1)\pmod {97}\\
&\equiv [(22^{2})^{2}-1]\pmod {97}\\
&\equiv [(-1)^{2}-1]\pmod {97}\\
&\equiv (1-1)\pmod {97}\\
&\equiv 0\pmod {97}.
\end{align*}
Therefore, ## 97\mid (2^{48}-1) ##.

 

[fresh_42]

I thought of something like
\begin{align*}
2^{11}&=2048=23\cdot 89 +1\\
33^2&=11^2\cdot 9=121\cdot 9=1089=11\cdot 97 +22\\
22^2&=11^2\cdot 4=121 \cdot 4= 484=4\cdot 97 +96
\end{align*}
In the end, it is only a matter of taste. I just found it uncomfortable that I had to use a calculator to verify your proof. Using the calculator would have allowed me to verify the statement on my own anyway, so where was the advantage to read the proof?

 

[fresh_42]

Another way to approach it is a trick that should always come to mind when even powers occur.

Set ##a=2^{11}=2048## and ##b=2^{6}=64.## Then
\begin{align*}
2^{44}-1&=(a^4-1)=(a^2-1)(a^2+1)\\&=(a-1)(a+1)(a^2+1)\\
&=\underbrace{2,047}_{89\,\mid 23\cdot 89}\cdot \underbrace{2,049}_{89\,\nmid } \cdot \underbrace{4,194,305}_{89\,\nmid }\\
&\\
2^{48}-1&=(b^8-1)=(b^4-1)(b^4+1)=(b^2-1)(b^2+1)(b^4+1)\\&=(b-1)(b+1)(b^2+1)(b^4+1)\\
&=\underbrace{63}_{97\,\nmid}\cdot \underbrace{65}_{97\,\nmid} \cdot \underbrace{4,097}_{97\,\nmid} \cdot \underbrace{16,777,217}_{97\,\mid 172,961\cdot 97}
\end{align*}

 

[SammyS]

I thought of something like
\begin{align*}
2^{11}&=2048=23\cdot 89 +1\\
33^2&=11^2\cdot 9=121\cdot 9=1089=11\cdot 97 +22\\
22^2&=11^2\cdot 4=121 \cdot 4= 484=4\cdot 97 +96
\end{align*}
In the end, it is only a matter of taste. I just found it uncomfortable that I had to use a calculator to verify your proof. Using the calculator would have allowed me to verify the statement on my own anyway, so where was the advantage to read the proof?

Another way to show ## \,33^2\equiv 22 \pmod{97}## .

##33^2=11\cdot 3\cdot 33=11\cdot 99 ##

Therefore, ## \,33^2\equiv 11\cdot 2 \pmod{97}##