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

  • Thread starter Math100
  • Start date
In summary: But, ## \,33^2=11\cdot 11 \cdot 3 \cdot 3=121\cdot 9\equiv 22 \pmod{97}## .Hence, ## \,33^2\equiv 22 \pmod{97}## .In summary, using the theory of congruences, we can verify that 89 divides 2 to the power of 44 minus 1 and 97 divides 2 to the power of 48 minus 1. This is shown by observing that 2 to the power of 11 is equivalent to 1 modulo 89 and 33 to the power of 2 is equivalent to 22 modulo 97. Therefore,
  • #1
Math100
802
222
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
  • #2
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.
 
  • #3
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) ##.
 
  • #4
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:
  • Like
Likes Math100
  • #5
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*}
 
  • Like
Likes Math100
  • #6
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

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

How do you prove that 89 divides (2^44-1) and 97 divides (2^48-1)?

To prove that a number divides another number, you need to show that the remainder when dividing the first number by the second number is equal to 0. In this case, we can use modular arithmetic to show that the remainder is 0 for both 89 and 97.

What is modular arithmetic?

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value. In this case, we are using modular arithmetic to show that the remainder when dividing (2^44-1) by 89 or (2^48-1) by 97 is equal to 0.

How do you apply modular arithmetic to this problem?

To apply modular arithmetic, we can use the property that (a^b) mod n = (a mod n)^b mod n. In this case, we can rewrite (2^44-1) as (2 mod 89)^44 mod 89, and (2^48-1) as (2 mod 97)^48 mod 97. Then, we can use a calculator or computer program to calculate the remainder for each expression, which will be 0 for both 89 and 97.

Why are these specific numbers (89 and 97) used in the problem?

These specific numbers were likely chosen because they are relatively large prime numbers, making it more challenging to prove that they divide the given expressions. Additionally, they have a special property called the Fermat's Little Theorem, which states that if p is a prime number, then a^(p-1) mod p = 1 for any integer a. This property can be used to simplify the calculations in this problem.

What is the significance of proving that these numbers divide the given expressions?

Proving that these numbers divide the given expressions is significant because it shows that the expressions are divisible by large prime numbers, which can have important applications in number theory and cryptography. It also demonstrates the power of modular arithmetic in solving mathematical problems.

Similar threads

Replies
1
Views
1K
Replies
2
Views
914
Replies
3
Views
1K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
5
Views
2K
Back
Top