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
492
2
avatar+474 

What is the greatest common divisor of \(2^{1001}-1\) and \(2^{1012}-1\)?

 Sep 22, 2018

Best Answer 

 #2
avatar+5226 
+2

The theorem being used here is that

 

\(gcd(a^n -1,~a^m-1) = a^{gcd(m,n)}-1\)

 

in this case \(n=1001,~m=1012\)

 

\(1001 = 7 \cdot 11 \cdot 13 \\ 1012 = 2 \cdot 11 \cdot 23 \\ \text{so clearly }gcd(1001,~1012)=11\\ 2^{11}-1 = 2047 \text{ as guest correctly computed}\)

 

The proof of this theorem can be found online

 Sep 22, 2018
 #1
avatar
+1

I think the GCD of ((2^1001) - 1), ((2^1012) - 1) =2^(1012 - 1001) - 1 =2^11 - 1 =2,047

 Sep 22, 2018
 #2
avatar+5226 
+2
Best Answer

The theorem being used here is that

 

\(gcd(a^n -1,~a^m-1) = a^{gcd(m,n)}-1\)

 

in this case \(n=1001,~m=1012\)

 

\(1001 = 7 \cdot 11 \cdot 13 \\ 1012 = 2 \cdot 11 \cdot 23 \\ \text{so clearly }gcd(1001,~1012)=11\\ 2^{11}-1 = 2047 \text{ as guest correctly computed}\)

 

The proof of this theorem can be found online

Rom Sep 22, 2018

11 Online Users