+0

# What is the greatest common divisor of $2^{1001}-1$ and $2^{1012}-1$?

0
234
2
+474

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

Sep 22, 2018

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