Problem
NT-B2-M01-P015 Two Bases
#15
★★★★☆ Level 4 of 5
Let \(a>b>0\), \( \gcd(a,b)=1 \). Prove that \( \gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)} \).
A common divisor is coprime to \(b\), so one can work with \(ab^{-1}\) modulo that divisor.
Let \(g=\gcd(m,n)\). The number \(a^g-b^g\) divides both expressions. Conversely, let \(d\) divide both. Since \( \gcd(b,d)=1 \), the inverse \(b^{-1}\pmod d\) exists. From \(a^m\equiv b^m\) and \(a^n\equiv b^n\), we get \((ab^{-1})^m\equiv1\) and \((ab^{-1})^n\equiv1\pmod d\). The Euclidean algorithm on the exponents gives \((ab^{-1})^g\equiv1\pmod d\). Hence \(a^g\equiv b^g\pmod d\), so \(d\mid a^g-b^g\).
This is a key template for later problems on multiplicative order.