Problem
NT-B1-M11-P020 GCD of Power Numbers
#20
★★★☆☆ Level 3 of 5
Prove that \(\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1\).
Repeat the Euclidean algorithm on the exponents.
If \(m\ge n\), then \(2^m-1=(2^{m-n})(2^n-1)+(2^{m-n}-1)\). Hence the GCD is unchanged when \((m,n)\) is replaced by \((m-n,n)\). Repeating the Euclidean algorithm on the exponents leads to \((d,d)\), where \(d=\gcd(m,n)\). The GCD is \(2^d-1\).
Important formula, presented in Book 1 through a familiar Euclidean idea.