Results 1 to 2 of 2

Thread: Divisibility (gcd) 16

  1. #1
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    54

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum