A problem taken from the exercises of Concrete Mathematics by Graham, Knuth, and Patashnik is as follows:
Prove that if $a\perp b$ and $a>b$ then
$$\gcd(a^m-b^m,a^n-b^n) = a^{\gcd(m,n)} – b^{\gcd(m,n)},\quad 0\leq m<n.$$
(In the notation of the book, $a\perp b$ means that $a$ and $b$ are relatively prime, i.e. $\gcd(a,b)=1$.)
I can not prove this equation. Can you please help me to prove this formula?
Best Answer
This is exercise 4.38. There is a hint to use Euclid's algorithm that you forgot to reproduce. There is also an answer (p. 503) that reads
$a^n-b^n =(a^m-b^m)(a^{n-m}b^0+a^{n-2m}b^m+\cdots+a^{n\bmod m}b^{n-m-n\bmod m})+b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m})$
What this means is that the first step of Euclid's algorithm reduces $\gcd(a^n-b^n,a^m-b^m)$ to $\gcd(a^m-b^m,b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m}))$. But $b^{m\lfloor n/m\rfloor}$ is relatively prime to $a^n-b^n$ since it divides the second term and is relatively prime to the first term; therefore it will be relatively prime to the $\gcd$ that is being computed, and we might as well remove that factor from the second argument of the $\gcd$. All in all this gives $$ \gcd(a^n-b^n,a^m-b^m) =\gcd(a^m-b^m,a^{n\bmod m}-b^{n\bmod m}). $$ Now iterating as in the Euclidean algorithm eventually gives $$ \gcd(a^m-b^m,a^n-b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}. $$