# Math Help - Help with g.c.d.

1. ## Help with g.c.d.

Show that if gcd(a,b)=1, and p is an odd prime, then

gcd( a+b , {(a^p)+(b^p)}/(a+b) ) = 1 or p

I've tried obvious ways to show it, and even expanded by binomial theorem, but of no use.

2. ## Re: Help with g.c.d.

First to type your question in LaTeX:

Show that if $\gcd(a,b)=1$, and $p$ is an odd prime, then $\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$ or $p$.

I think that one route to try comes from the observation that the GCD of $A$ and $B$ divides any "linear combination" of them; that is, it will divide any number of the form $Am+Bn$ for any integers $m, n$. So, in particular, $\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)$ must divide

$\frac{a^p+b^p}{a+b}\cdot 1-(a+b)(a+b)^{n-2}=\frac{a^p+b^p}{a+b}-(a+b)^{n-1}=\frac{a^p+b^p}{a+b}-\frac{(a+b)^n}{a+b}$

The nice part is that this shaves off $a^p$ and $b^p$ from the numerator and leaves you with terms that look like $\binom{p}{k}a^kb^{p-k}$ where $k$ ranges between $1$ and $p-1$. And in particular, you may know that this kind of term is divisible by $p$, which seems helpful for your statement.

Maybe you can play around with this for a while and see where it goes.

3. ## Re: Help with g.c.d.

Originally Posted by roninpro
First to type your question in LaTeX:

Show that if $\gcd(a,b)=1$, and $p$ is an odd prime, then $\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1$ or $p$.

I think that one route to try comes from the observation that the GCD of $A$ and $B$ divides any "linear combination" of them; that is, it will divide any number of the form $Am+Bn$ for any integers $m, n$. So, in particular, $\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)$ must divide

$\frac{a^p+b^p}{a+b}\cdot 1-(a+b)(a+b)^{n-2}=\frac{a^p+b^p}{a+b}-(a+b)^{n-1}=\frac{a^p+b^p}{a+b}-\frac{(a+b)^n}{a+b}$

The nice part is that this shaves off $a^p$ and $b^p$ from the numerator and leaves you with terms that look like $\binom{p}{k}a^kb^{p-k}$ where $k$ ranges between $1$ and $p-1$. And in particular, you may know that this kind of term is divisible by $p$, which seems helpful for your statement.

Maybe you can play around with this for a while and see where it goes.
Thank you, I'll give it a try.

4. ## Re: Help with g.c.d.

Simple notation step helps. Write $c=a+b$, then the Binomial Theorem gives $a^p+b^p=(c-b)^p+b^p=\binom{p}{0}c^p-\binom{p}{1}c^{p-1}b+\cdots-\binom{p}{p-2}c^2b^{p-2}+\binom{p}{p-1}cb^{p-1}$ (note that the last term of $(c-b)^p$ is $-\binom{p}{p}b^p=-b^p$).

Divide both sides by $c$; hence $\frac{a^p+b^p}{c}=\binom{p}{0}c^{p-1}-\binom{p}{1}c^{p-2}b+\cdots-\binom{p}{p-2}cb^{p-2}+\binom{p}{p-1}b^{p-1}$.
Then factor out $c$, by doing so we arrive at the following form: $\frac{a^p+b^p}{c}=cN+\binom{p}{p-1}b^{p-1}=cN+pb^{p-1}$ for some integer $N$.

It's important to see that $(a+b,b^{p-1})=1$(explain this) and so $(c,b^{p-1})=1$.
Let $g=(c,\frac{a^p+b^p}{c})=(c,cN+pb^{p-1})$. Because $g|c$ and $(c,b^{p-1})=1$ it's true that $(g,b^{p-1})=1$. By definition, $g$ must divide $(cN+bp^{p-1})-c\cdot N=pb^{p-1}$. But from $(g,b^{p-1})=1$ and $g|pb^{p-1}$ we conclude that $g|p$.

Since $p$ is prime $g=1,$ or $p$.

Thanks

6. ## Re: Help with g.c.d.

Originally Posted by melese
Simple notation step helps. Write $c=a+b$, then the Binomial Theorem gives $a^p+b^p=(c-b)^p+b^p=\binom{p}{0}c^p-\binom{p}{1}c^{p-1}b+\cdots-\binom{p}{p-2}c^2b^{p-2}+\binom{p}{p-1}cb^{p-1}$ (note that the last term of $(c-b)^p$ is $-\binom{p}{p}b^p=-b^p$).

Divide both sides by $c$; hence $\frac{a^p+b^p}{c}=\binom{p}{0}c^{p-1}-\binom{p}{1}c^{p-2}b+\cdots-\binom{p}{p-2}cb^{p-2}+\binom{p}{p-1}b^{p-1}$.
Then factor out $c$, by doing so we arrive at the following form: $\frac{a^p+b^p}{c}=cN+\binom{p}{p-1}b^{p-1}=cN+pb^{p-1}$ for some integer $N$.

It's important to see that $(a+b,b^{p-1})=1$(explain this) and so $(c,b^{p-1})=1$.
Let $g=(c,\frac{a^p+b^p}{c})=(c,cN+pb^{p-1})$. Because $g|c$ and $(c,b^{p-1})=1$ it's true that $(g,b^{p-1})=1$. By definition, $g$ must divide $(cN+bp^{p-1})-c\cdot N=pb^{p-1}$. But from $(g,b^{p-1})=1$ and $g|pb^{p-1}$ we conclude that $g|p$.

Since $p$ is prime $g=1,$ or $p$.
Wow, amazing. Thanks a lot. I've been trying so hard to solve this one but I guess I'm not that good.
P.S. ( a+b , b^p-1)=1 because (a,b)=1, so (a,b^p-1)=1 and hence...