# Divisibility (gcd) 16

• Dec 21st 2008, 07:22 AM
Sea
Divisibility (gcd) 16
$a,b \in \mathbb{Z^+} , (a,b)=1 ,$

$n \in\mathbb{N} ,$

Show that:

$(\frac{a^n-b^n}{a-b},a-b)=1$ or $n$
• Dec 21st 2008, 09:20 AM
PaulRS
Take $a=5$ ; $b=2$ and $n=6$

It should be $\left(\frac{a^n-b^n}{a-b},a-b\right)|n$

Now, the proof I've found is nasty

We have $
\tfrac{{a^n - b^n }}
{{a - b}} = a^{n - 1} + a^{n - 2} \cdot b + ... + a \cdot b^{n - 2} + b^{n - 1}
$

Let's define $M=\left(\frac{a^n-b^n}{a-b},a-b\right)$

M divides any linear combination ( with integer coeficients) of those 2.

So M divides: $
a^{n - 1} + a^{n - 2} \cdot b + ... + a \cdot b^{n - 2} + b^{n - 1} - a^{n - 2} \cdot \left( {a - b} \right)
$
i.e. $
M\left| {\left( {2 \cdot a^{n - 2} \cdot b + ... + a \cdot b^{n - 2} + b^{n - 1} } \right)} \right.
$

Again: $
M\left| {\left( {\left[ {2 \cdot a^{n - 2} \cdot b + ... + a \cdot b^{n - 2} + b^{n - 1} } \right] + b^{n - 2} \cdot \left( {a - b} \right)} \right)} \right.
$
Thus: $
M\left| {\left( {2 \cdot a^{n - 2} \cdot b + ... + 2a \cdot b^{n - 2} } \right)} \right.
$

And this goes on: $
M\left| {\left( {\left[ {2 \cdot a^{n - 2} \cdot b + ... + 2a \cdot b^{n - 2} } \right] - 2 \cdot a^{n - 3} b \cdot \left( {a - b} \right)} \right)} \right.
$
$
\Rightarrow M\left| {\left( {\left[ {3 \cdot a^{n - 3} \cdot b^2 + ... + 2a \cdot b^{n - 2} } \right]} \right)} \right.
$

$
M\left| {\left( {3 \cdot a^{n - 3} \cdot b^2 + a^{n - 4} \cdot b^3 + ... + a^3 \cdot b^{n - 4} + 3a^2 \cdot b^{n - 3} } \right)} \right.
$

We keep on eliminating terms, the idea is to have only 1 term in the end.

If $n$ is even we eventually get: $
M\left| {\left( {n \cdot a^{\tfrac{n}
{2}} \cdot b^{\tfrac{n}
{2} - 1} } \right)} \right.
$
( or the symmetric)

Whereas if n is odd: $
M\left| {\left( {n \cdot a^{\tfrac{{n - 1}}
{2}} \cdot b^{\tfrac{{n - 1}}
{2}} } \right)} \right.
$

But, since M divides a-b and (a,b)=1 then $(M,a)=1$ and $(M,b)=1$ thus we must have $M|n$