Results 1 to 2 of 2

Math Help - Divisibility (gcd) 16

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

    Divisibility (gcd) 16

    a,b \in \mathbb{Z^+}  , (a,b)=1 ,

     n \in\mathbb{N} ,

    Show that:

     (\frac{a^n-b^n}{a-b},a-b)=1 or n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Take a=5 ; b=2 and n=6

    It should be \left(\frac{a^n-b^n}{a-b},a-b\right)|n

    Now, the proof I've found is nasty

    We have <br />
\tfrac{{a^n  - b^n }}<br />
{{a - b}} = a^{n - 1}  + a^{n - 2}  \cdot b + ... + a \cdot b^{n - 2}  + b^{n - 1} <br />

    Let's define 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: <br />
a^{n - 1}  + a^{n - 2}  \cdot b + ... + a \cdot b^{n - 2}  + b^{n - 1}  - a^{n - 2}  \cdot \left( {a - b} \right)<br />
i.e. <br />
M\left| {\left( {2 \cdot a^{n - 2}  \cdot b + ... + a \cdot b^{n - 2}  + b^{n - 1} } \right)} \right.<br />

    Again: <br />
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.<br />
Thus: <br />
M\left| {\left( {2 \cdot a^{n - 2}  \cdot b + ... + 2a \cdot b^{n - 2} } \right)} \right.<br />

    And this goes on: <br />
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.<br />
<br />
 \Rightarrow M\left| {\left( {\left[ {3 \cdot a^{n - 3}  \cdot b^2  + ... + 2a \cdot b^{n - 2} } \right]} \right)} \right.<br />

    <br />
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.<br />

    We keep on eliminating terms, the idea is to have only 1 term in the end.

    If n is even we eventually get: <br />
M\left| {\left( {n \cdot a^{\tfrac{n}<br />
{2}}  \cdot b^{\tfrac{n}<br />
{2} - 1} } \right)} \right.<br />
( or the symmetric)

    Whereas if n is odd: <br />
M\left| {\left( {n \cdot a^{\tfrac{{n - 1}}<br />
{2}}  \cdot b^{\tfrac{{n - 1}}<br />
{2}} } \right)} \right.<br />

    But, since M divides a-b and (a,b)=1 then (M,a)=1 and (M,b)=1 thus we must have 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: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum