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

  • Thread starter Thread starter Math100
  • Start date Start date
AI Thread Summary
The discussion provides a proof that 89 divides (2^44 - 1) and 97 divides (2^48 - 1) using modular arithmetic. It demonstrates that 2^11 is congruent to 1 modulo 89, leading to the conclusion that 89 divides (2^44 - 1). Similarly, it shows that 2^6 is congruent to -33 modulo 97, allowing the conclusion that 97 divides (2^48 - 1). Participants express a desire for clearer steps in the proof, particularly regarding the congruences used. Overall, the proof confirms the divisibility claims through detailed modular calculations.
Math100
Messages
813
Reaction score
229
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) ##.
 
Physics news on Phys.org
Math100 said:
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.
 
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) ##.
 
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?
 
Last edited:
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*}
 
fresh_42 said:
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}##
 
  • Like
Likes fresh_42 and Math100
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
Back
Top