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

RektTheNoob Sep 22, 2018

#2**+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**+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**+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