2023 · Q1
What is the largest number which divides both 2³⁵ - 1 and 2⁹¹ - 1?
Elementary MathematicsHCF and LCM
- A34
- B90
- C127
- D129
Explanation
For powers of two, gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1. Here gcd(35, 91) = 7, since 91 = 2·35 + 21, 35 = 21 + 14 and 21 = 2·14 + 7. Hence the greatest common divisor is 2^7 − 1 = 127, which divides both numbers and every common divisor divides it. The largest such number is 127 (C).