1. ## Divisibility (gcd) 16

$\displaystyle a,b \in \mathbb{Z^+} , (a,b)=1 ,$

$\displaystyle n \in\mathbb{N} ,$

Show that:

$\displaystyle (\frac{a^n-b^n}{a-b},a-b)=1$ or $\displaystyle n$

2. Take $\displaystyle a=5$ ; $\displaystyle b=2$ and $\displaystyle n=6$

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

Now, the proof I've found is nasty

We have $\displaystyle \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 $\displaystyle 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: $\displaystyle 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. $\displaystyle M\left| {\left( {2 \cdot a^{n - 2} \cdot b + ... + a \cdot b^{n - 2} + b^{n - 1} } \right)} \right.$

Again: $\displaystyle 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: $\displaystyle M\left| {\left( {2 \cdot a^{n - 2} \cdot b + ... + 2a \cdot b^{n - 2} } \right)} \right.$

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

$\displaystyle 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 $\displaystyle n$ is even we eventually get: $\displaystyle 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: $\displaystyle 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 $\displaystyle (M,a)=1$ and $\displaystyle (M,b)=1$ thus we must have $\displaystyle M|n$