Problem
NT-B1-M02-P021 General Formula for \(a^m-1\)
#21
★★★★☆ Level 4 of 5
Prove that for integer \(a>1\) and positive \(m,n\),
\[\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1.\]
Run the Euclidean algorithm on the exponents: if \(m=qn+r\), then \(a^m-1\) modulo \(a^n-1\) is related to \(a^r-1\).
Let \(m\ge n\) and \(m=qn+r\). Since \(a^n\equiv1\pmod{a^n-1}\), we have \(a^m=a^{qn+r}\equiv a^r\pmod{a^n-1}\). Therefore \(\gcd(a^m-1,a^n-1)=\gcd(a^r-1,a^n-1)\). This is exactly the Euclidean step for the exponent pair \((m,n)\). Repeating, we reach \(d=\gcd(m,n)\). The GCD is \(a^d-1\).
This is the key formula of the module and a bridge to stronger number theory.