# How to prove $\gcd(a^m-b^m,a^n-b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}$?

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$.)

• Hint: Start by showing the indicated expression is a common divisor. Then examine the respective quotients. Dec 19, 2012 at 15:58
• I've added the hypotheses on $a$ and $b$ that were stated in the problem. Dec 19, 2012 at 16:00
• What does 'a' is perpendicular to 'b' mean? Dec 19, 2012 at 16:00
• a⊥b means a is relatively prime with respect to b Dec 19, 2012 at 16:02
• Feb 21, 2015 at 16:15

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)}.$$

• Many Many Thanks Dec 19, 2012 at 16:33
• I can not solve 24 no. problem of 4th chapter .Can you plz help me to solve it ? Dec 21, 2012 at 2:11
• Why don't you post it (with reference) as a separate question, explain what you tried and why the answer on page 502 is insufficient for you to get it? The one-question-per-question format works best on this site. Dec 21, 2012 at 5:47

Outline of a proof:

Let $d\mid a^n-b^n$ and $d\mid a^m-b^m$.

The "slick" solution is to show that if $mx+ny=\gcd(m,n)$, then since:

$$a^m\equiv b^m\pmod d$$

and

$$a^n\equiv b^n\pmod d$$

Then:

$$a^{(m,n)}=(a^m)^x (a^n)^y \equiv (b^m)^x(b^n)^y = b^{(m,n)}\pmod d$$

The only tricky part here is that you need to understand that we can invert $a$ and $b$ modulo $d$ since $a\perp b$ means that $d\perp a$ and $d\perp b$. So, although $x$ or $y$ might be negative, you can work around this by taking care.

• a^n-b^n = (a^m-b^m) ( a^(n-m)b^0 + a^(n-2m)b^m + .............................. + a^(r)b^(n-m-r) ) + b^(m* floor(n/m) (a^r-B^r)) Can I take any decision of gcd(a^n-b^n,a^m-b^m) from this equations ? Dec 19, 2012 at 16:13
• I understand the solution . Many Many Thanks . Dec 19, 2012 at 16:23