+0  
 
0
125
2
avatar+461 

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

RektTheNoob  Sep 22, 2018

Best Answer 

 #2
avatar+3187 
+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

Rom  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

Guest Sep 22, 2018
 #2
avatar+3187 
+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

17 Online Users

avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.