+0

# gcd

0
130
2

What is the greatest common divisor of 2^1001 - 1 and 2^7 - 1?

Dec 31, 2020

#1
0

2^1001 - 1= 23 × 89 × 127 × 911 × 6007 × 8191 × 724153 × 112 901153 × 23140 471537 × 158822 951431 × 581283 643249 112959 × 5 782172 113400 990737 × 1820 949348 989208 563134 934454 867370 417241 731442 757253 769027 660122 025220 531154 643424 727557 175913 816984 478330 956518 484750 019883 125787 765755 778716 216864 601050 903144 122991 701474 321184 972747 689246 938140 437077 841940 203833 (214 digits) (Composite)

2^7 - 1 = 127

Therefore the GCD of [2^1001 - 1,  2^7 - 1]==127

Dec 31, 2020
#2
+25658
+1

What is the greatest common divisor(gcd) of $$2^{1001} - 1$$ and $$2^7 - 1$$?

Formula: $$\boxed{ gcd(a^n -1,~a^m-1) = a^{gcd(m,n)}-1 }$$

$$\begin{array}{|rcll|} \hline a &=& 2 \\ n &=& 1001 \\ m &=& 7 \\ \hline gcd(a^n -1,~a^m-1) &=& a^{gcd(m,n)}-1 \\ gcd(2^{1001} - 1,~2^{7} - 1) &=& 2^{gcd(1001,7)}-1 \quad | \quad \mathbf{gcd(1001,7)= 7} \\ gcd(2^{1001} - 1,~2^{7} - 1) &=& 2^{7}-1 \\ \mathbf{gcd(2^{1001} - 1,~2^{7} - 1)} &=& \mathbf{127} \\ \hline \end{array}$$

Jan 1, 2021
edited by heureka  Jan 1, 2021