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?

  • 0
    Hint: Start by showing the indicated expression is a common divisor. Then examine the respective quotients.2012-12-19
  • 0
    I've added the hypotheses on $a$ and $b$ that were stated in the problem.2012-12-19
  • 1
    What does 'a' is perpendicular to 'b' mean?2012-12-19
  • 0
    Alternatively, assuming $m>n$, show that if $d|a^m-b^m$ and $d|a^n-b^n$ then $d|a^{m-n}-b^{m-n}$. This lets you prove the theorem by induction.2012-12-19
  • 0
    what does a⊥b mean ?2012-12-19
  • 1
    a⊥b means a is relatively prime with respect to b2012-12-19
  • 0
    @SultanAhmedSagor When you write a comment, please be specific. "yes I try to do that > But then ?? ". It doesn't mean anything, given that you've received at least two suggestions2012-12-19
  • 0
    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 ?2012-12-19
  • 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
    Many Many Thanks2012-12-19
  • 0
    I can not solve 24 no. problem of 4th chapter .Can you plz help me to solve it ?2012-12-21
  • 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
    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 ?2012-12-19
  • 0
    I understand the solution . Many Many Thanks .2012-12-19