Results 1 to 6 of 6

Math Help - Help with g.c.d.

  1. #1
    Newbie
    Joined
    Oct 2011
    From
    Shillong
    Posts
    4

    Help with g.c.d.

    Please help me solve this:

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    From
    Shillong
    Posts
    4

    Re: Help with g.c.d.

    Quote Originally Posted by roninpro View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2011
    From
    Shillong
    Posts
    4

    Re: Help with g.c.d.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2011
    From
    Shillong
    Posts
    4

    Re: Help with g.c.d.

    Quote Originally Posted by melese View Post
    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...
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum