7
$\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<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?

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

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Many Many Thanks $\endgroup$ Dec 19, 2012 at 16:33
  • $\begingroup$ I can not solve 24 no. problem of 4th chapter .Can you plz help me to solve it ? $\endgroup$ Dec 21, 2012 at 2:11
  • $\begingroup$ 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. $\endgroup$ Dec 21, 2012 at 5:47
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$ Dec 19, 2012 at 16:13
  • $\begingroup$ I understand the solution . Many Many Thanks . $\endgroup$ Dec 19, 2012 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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