# How to show that: $\gcd\left( {a^n-b^n \over a-b} ,a-b\right)=\gcd(n d^{n-1},a-b )$

How to show that:

$$\gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b )$$ $a,b\in \mathbb Z$

where $d=\gcd(a,b)$?

• $\gcd$ is the greatest common divisor.
-
What is GCD of a single number as in $GCD \bigg( {a^n-b^n \over a-b} \bigg)$? –  draks ... Nov 29 '12 at 9:52
@draks sorry,question is new. –  World Nov 29 '12 at 10:07

We have $\large\ d=(a,b)\ ,\$ thus $\large\ \exists\ A,B\ \ \ a=Ad,\ b=Bd,\ (A,B)=1$

$\large\left(\LARGE\frac{a^n-b^n}{a-b}\large,a-b\right)=(n d^{n-1},a-b)$
$\large\ d\left(d^{n-2}\cdot\LARGE\frac{A^{\ n}-B^{\ n}}{A-B}\large,A-B\right)=d(n d^{n-2},A-B)$

Let $\large\ m=A-B\ ,\ \ \ \$ then $\large\ (m,B)=1$

$\large\ \left(d^{n-2}\cdot\LARGE\frac{(B+m)^n-B^n}{m}\large,m\right)=(nd^{n-2},m)$
$\large\ \left(d^{n-2}\cdot(nB^{n-1}+Qm),m\right)=(nd^{n-2},m)\ \ \ \$ for some integer Q
$\large\ \left(nd^{n-2}B^{n-1},m\right)=(nd^{n-2},m)\ ,\ \$ which is due to $\large (m,B)=1$.

-
thanks for help. I don't know line 5 to 6 ? –  World Nov 29 '12 at 11:14
@World - See Binomial Expansion –  Egor Skriptunoff Nov 29 '12 at 11:46
1)mQ is $m \Big( {n \choose 2} B^{n-2} + ... \Big)$ ? 2) how to remove Qm from expression $\large\ \left(d^{n-2}\cdot(nB^{n-1}+Qm),m\right)=(nd^{n-2},m)$ –  World Nov 29 '12 at 12:17
@World - 1) Yes, 2) Using (x,y)=(x+qy,y) –  Egor Skriptunoff Nov 29 '12 at 12:26

Putting $c=a-b,$ we get, $$(a-b, \frac{a^n-b^n}{a-b})=(c, \frac{(b+c)^n-b^n}c)=(c,\binom n 1 b^{n-1}+\binom n 2 b^{n-2}c+\cdots+c^{n-1})=(c,nb^{n-1})$$

As $(c,b)=(a-b,b)=(a,b)=d,$ let $\frac c C=\frac b B=d$ so that $(B,C)=1$

$$(c,nb^{n-1})=(Cd,nB^{n-1}d^{n-1})=d(C,nB^{n-1}d^{n-2})=d(C,nd^{n-2})$$ as $(B,C)=1$

$$(c,nb^{n-1})=d(C,nd^{n-2})=(Cd,nd^{n-1})=(c,nd^{n-1})=(a-b, nd^{n-1})$$

-