Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Hint: Start by showing the indicated expression is a common divisor. Then examine the respective quotients. –  hardmath Dec 19 '12 at 15:58
    
I've added the hypotheses on $a$ and $b$ that were stated in the problem. –  Zev Chonoles Dec 19 '12 at 16:00
1  
What does 'a' is perpendicular to 'b' mean? –  Isomorphism Dec 19 '12 at 16:00
    
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. –  Thomas Andrews Dec 19 '12 at 16:00
1  
a⊥b means a is relatively prime with respect to b –  Way to infinity Dec 19 '12 at 16:02

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Many Many Thanks –  Way to infinity Dec 19 '12 at 16:33
    
I can not solve 24 no. problem of 4th chapter .Can you plz help me to solve it ? –  Way to infinity Dec 21 '12 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. –  Marc van Leeuwen Dec 21 '12 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.

share|improve this answer
    
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 ? –  Way to infinity Dec 19 '12 at 16:13
    
I understand the solution . Many Many Thanks . –  Way to infinity Dec 19 '12 at 16:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.