# Show that $\gcd\left(\frac{a^n-b^n}{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)$?

Note $\$ Some of the answers below were merged from this question. The answers (and their comments) may depend on context provided in that question.

-
what is (a,b)? gcd of a and b? –  ir7 Feb 2 '14 at 4:44
Yeah (a,b) = gcd(a,b). I'll change it to be all gcd so it's consistent. –  Adam Staples Feb 2 '14 at 4:45
So, for $n=2$, you want: $gcd(a+b,a-b) = gcd(2\cdot gcd(a,b), a-b)$. –  ir7 Feb 2 '14 at 4:55
Yeah that would be true. If we were doing induction I'd say n = 1 would be the base case. (a-b,a-b) = a-b. (1,a-b) = 1. Wait I'm confused now. –  Adam Staples Feb 2 '14 at 4:59
gcd(x,y) = gcd(x+my,y) for any integer m, and gcd(x,y,z) = gcd(gcd(x,y),z), so gcd(a+b,a-b)=gcd(2a,a-b) = gcd(2b,a-b) = gcd(2a,2b,a-b) = gcd(gcd(2a,2b),a-b) =gcd(2gcd(a,b),a-b). –  ir7 Feb 2 '14 at 5:17

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

${\rm mod}\ \color{#c00}{a\!-\!b}\!:\ c\, := a^{n-1}\!+a^{n-2}b+\cdots+\!b^{n-1}\!\equiv\!\overbrace{\color{#0a0}{n\,a^{n-1}}}^{\large {\rm by}\,\ \color{#c00}{b\,\equiv\, a}}\!\equiv\!\overbrace{\color{#0a0}{n\,b^{n-1}}}^{\large {\rm by}\,\ \color{#c00}{a\,\equiv\, b}}\!.\,$ By $\rm\color{#90f}{FD}$ = Freshman's Dream

\ \underbrace{(a\!-\!b,c)\, =\, (a\!-\!b,\color{#0a0}{na^{n-1},nb^{n-1}})}_{\Large (a-b,\,c)\,\ =\ \ (a-b,\ \ c\,\ {\rm mod}\,\ \color{#c00}{a-b})\ \ } \underset{\begin{align}\\[-2pt] \large{\rm by\ \, Euclid}\end{align}\qquad\qquad\qquad}{=\, (a\!-\!b,n(a^{n-1},b^{n-1}))} \overset{\color{#90f}{\rm FD}}= (a\!-\!b,n(a,b)^{n-1})\ \ \ {\bf QED}\quad

-
Yes this makes everything look great! Thank you very much! I think it was the reducing mod a-b that simplified this problem a lot! It didn't occur to me. –  Adam Staples Feb 2 '14 at 5:18
This is my first time learning about Freshman's Dream so I would like to learn about this theorem. –  Adam Staples Feb 2 '14 at 5:21
@Adam Whenever one seeks to simplify a gcd the first thing one should try is reducing the argument(s) mod the smallest/simplest argument (the key idea behind the Euclidean algorithm). The Freshman's Dream for gcds and ideals is discussed in many MSE posts. –  Bill Dubuque Feb 2 '14 at 5:30
Note  This answer was merged here from this question, where it was the accepted answer. –  Bill Dubuque Apr 20 at 22:10

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

-

Here are some major thoughts:

• Reduce $a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1}$ modulo $a-b$ by setting $a=b$.

• Note $a=(a,b)\cdot\frac{a}{(a,b)}$ and $\left(\frac{a}{(a,b)},a-b\right)=\left(\frac{a}{(a,b)},b\right)=\frac{(a,b)}{(a,b)}=1$.

-
Do you think that this can lead to a complete proof without more major thoughts? If so, I'm very interested to see how. –  Bill Dubuque Feb 2 '14 at 5:16
The first point you make explains perfectly my statement that $gcd(a,b)^{n−1}$ is going to be of the same order as $\frac{(a^{n}-b^{n})}{a-b}$ and explains the n in the front perfectly. –  Adam Staples Feb 2 '14 at 5:16
It's not clear to me how you plan to complete the proof this way. Could you please write out the details. I am very interested to see proofs that are essentially different than the one I gave. I vaguely recall there are at least a couple other ways, but I cannot recall the details at the moment. –  Bill Dubuque Feb 2 '14 at 5:24
@Bill If $x=\frac{a}{(a,b)}$ is coprime to $y=a-b$ then so is $x^{n-1}$, hence $(n(a,b)^{n-1}x^{n-1},y)$ equals $(n(a,b)^{n-1},y)$. This is an additional major fact involved, but $(x,y)=1\Rightarrow (zx^m,y)=(z,y)$ is intuitive and well-known enough that I didn't think I needed to point out its usage. –  anon Feb 3 '14 at 9:52
@anon Thanks. So it seems to boil down to essentially the same argument I gave. I was hoping that it might be one of the other proofs that I have no luck recalling at the moment. If anyone knows other ways of proof then I'd be interested to hear about them. –  Bill Dubuque Feb 3 '14 at 15:23

This answer does the case $\gcd(a,b)=1$ only.

**Main idea:**$\let\v\nu\let\geq\geqslant$ investigate how many times a prime divides $a^n-b^n$.

For $m\in\mathbb N$, let $\v_p(m)$ denote the exponent (multiplicity) of the prime $p$ in the prime factorisation of $m$.

Lemma (Lifting The Exponent) let $a,b\in\mathbb Z$, $p\mid a-b$ prime, $p\nmid a$ and $n\in\mathbb N$.

1. If $p\nmid n$, then $$\v_p(a^n-b^n)=\v_p(a-b).\tag{1}$$

2. If $p$ is odd, then $$\v_p(a^n-b^n)=\v_p(a-b)+\v_p(n).\tag{2}$$

3. If $p=2$ and $4\mid a-b$, then $$\v_2(a^n-b^n)=\v_2(a-b)+\v_2(n).\tag{3}$$

4. If $p=2$ and $2\mid n$, then $$\v_2(a^n-b^n)=\v_2(a^2-b^2)+\v_2(\tfrac n2).\tag{4}$$

Proof. See here (Lemma 1, Theorem 1, Theorem 2, Theorem 4)
Note that 1. is contained in 2. and 3. except when $p=2$ and $4\nmid a-b$.
4. is an easy consequence of 3. by letting $a\mapsto a^2$, $b\mapsto b^2$ and $n\mapsto\frac n2$.

Let $p$ be a prime divisor of $a-b$. Because $\gcd(a,b)=1$, we have $p\nmid a$. We'll prove that $$\v_p\left(\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)\right)=\v_p(\gcd(n,a-b)).$$

If $p$ is odd or $p=2$ and $4\mid a-b$, then $\v_p\left(\frac{a^n-b^n}{a-b}\right)=\v_p(n)$ by $(2),(3)$, hence

\begin{align*}\v_p\left(\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)\right)&=\min\left(\v_p\left(\frac{a^n-b^n}{a-b}\right),\v_p(a-b)\right)\\ &=\min(\v_p(n),\v_p(a-b))\\ &=\v_p(\gcd(n,a-b)).\end{align*}

The only case left is $p=2$ and $4\nmid a-b$.
If $n$ is odd, then by $(1)$ we know that $\frac{a^n-b^n}{a-b}$ is odd too.
If $n$ is even, $(4)$ gives that $\v_p(a^n-b^n)\geq\v_p(a-b)+1$, hence $\frac{a^n-b^n}{a-b}$ is even.

Either way, $$\v_2\left(\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)\right)=\v_2(\gcd(n,a-b)).$$

-