We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
41
3
avatar

What are the two smallest prime factors of 2^{1024} - 1?

 Nov 15, 2019
 #1
avatar+2482 
0
 

Hint: \((a^2-b^2)=(a+b)(a-b)\)

.
 Nov 15, 2019
 #2
avatar
0

2^1024 -1 = 3 x 5 x 17 x 257 x 641 x 65537 x 274177 x 2424833 x 6700417 x 67280421310721.........etc

 Nov 15, 2019
 #3
avatar+23516 
+2

What are the two smallest prime factors of \(2^{1024} - 1\)?

 

\(\begin{array}{|rcll|} \hline && 2^{1024} - 1 \\ &=& \left( 2^{512} - 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{256} - 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{128} - 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{64} - 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{32} - 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{16} - 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{8} - 1\right) \left( 2^{8} + 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{4} - 1\right) \left( 2^{4} + 1\right) \left( 2^{8} + 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{2} - 1\right) \left( 2^{2} + 1\right) \left( 2^{4} + 1\right) \left( 2^{8} + 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& \left( 2^{1} - 1\right) \left( 2^{1} + 1\right) \left( 2^{2} + 1\right) \left( 2^{4} + 1\right) \left( 2^{8} + 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ &=& 1\times 3 \times 5 \times \left( 2^{4} + 1\right) \left( 2^{8} + 1\right) \left( 2^{16} + 1\right) \left( 2^{32} + 1\right) \left( 2^{64} + 1\right) \left( 2^{128} + 1\right) \left( 2^{256} + 1\right) \left( 2^{512} + 1\right) \\ \hline \end{array} \)

 

The two smallest prime factors are 3 and 5, they are also the smallest possible odd prime numbers,

all factors are odd,

so that the 2 as the only even prime number cannot be included

 

laugh

 Nov 15, 2019

7 Online Users