6
$\begingroup$

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

(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?

  • 1
    Related: http://math.stackexchange.com/questions/74732015-02-21

2 Answers 2

4

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

  • 0
    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.2012-12-21
3

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.

  • 0
    I understand the solution . Many Many Thanks .2012-12-19