Results 1 to 5 of 5

Thread: Divisibility (gcd) 8

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

    Divisibility (gcd) 8

    Show that: $\displaystyle m,n ,a \in \mathbf{Z^{+}} $ and $\displaystyle a>1 $


    $\displaystyle \Rightarrow (a^{m}-1 , a^{n}-1)=a^{(m,n)}-1$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Let $\displaystyle (m,n) = d$ and $\displaystyle (a^m - 1, a^n -1) = l$

    $\displaystyle d|m \Rightarrow a^d - 1 | a^m - 1$

    $\displaystyle d|n \Rightarrow a^d - 1 | a^n - 1$

    Thus $\displaystyle a^d - 1 | l $. -----------------(1)

    By Bezout's identity we know that there exists non negative integers x and y such that $\displaystyle mx = ny + d$.

    $\displaystyle (a^m - 1, a^n -1) = l \Rightarrow l| a^m - 1 \Rightarrow l| a^{mx} - 1$

    But $\displaystyle a^{mx} - 1 = (a^{ny} - 1)a^d + a^d - 1$

    Thus $\displaystyle l| a^{mx} - 1 \Rightarrow l|a^d - 1$ -------------(2)

    (1) and (2) imply $\displaystyle l = a^d -1$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    54
    I don't know...

    $\displaystyle d|m$ (Why?) $\displaystyle \Rightarrow a^d - 1 | a^m - 1
    $
    $\displaystyle d|n$ (Why?) $\displaystyle \Rightarrow a^d - 1 | a^n - 1$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by Sea View Post
    I don't know...

    $\displaystyle d|m$ (Why?) $\displaystyle \Rightarrow a^d - 1 | a^m - 1
    $
    $\displaystyle d|n$ (Why?) $\displaystyle \Rightarrow a^d - 1 | a^n - 1$
    Consider the geometric series of $\displaystyle a^d$ :
    $\displaystyle \sum_{k=0}^{m/d} (a^d)^k=\sum_{k=0}^{m/d} a^{dk}=\frac{a^m-1}{a^d-1}$
    (m/d is an integer since d|m)

    The LHS is an integer, so the RHS has to be an integer. Hence $\displaystyle a^d-1$ divides $\displaystyle a^m-1$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    A slightly different way.

    We have $\displaystyle
    \left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^n - 1} \right)} \right. \wedge \left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^m - 1} \right)} \right.
    $ (as Moo points out) thus $\displaystyle
    \left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^n - 1,a^m - 1} \right)} \right.
    $ (1)

    Now let $\displaystyle q$ be a common divisor of $\displaystyle a^n-1$ and $\displaystyle a^m-1$ i.e. $\displaystyle
    a^n \equiv 1\left( {\bmod .q} \right) \wedge a^m \equiv 1\left( {\bmod .q} \right)
    $

    From the first congruence we get $\displaystyle
    \left. {{\text{ord}}_q \left( a \right)} \right|n
    $ and from the second $\displaystyle
    \left. {{\text{ord}}_q \left( a \right)} \right|m
    $ thus it must be that $\displaystyle
    \left. {{\text{ord}}_q \left( a \right)} \right|\left( {n,m} \right)
    $ hence $\displaystyle
    a^{\left( {n,m} \right)} \equiv 1\left( {\bmod .q} \right)
    $

    So every common divisor divides $\displaystyle
    a^{\left( {n,m} \right)} - 1
    $ and by (1) we are done (because it's the greatest possible)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum