Results 1 to 5 of 5

Math Help - Divisibility (gcd) 8

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

    Divisibility (gcd) 8

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


    \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 (m,n) = d and (a^m - 1, a^n -1) = l

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

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

    Thus a^d - 1 | l . -----------------(1)

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

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

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

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

    (1) and (2) imply 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
    50
    I don't know...

    d|m (Why?) \Rightarrow a^d - 1 | a^m - 1<br />
    d|n (Why?) \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...

    d|m (Why?) \Rightarrow a^d - 1 | a^m - 1<br />
    d|n (Why?) \Rightarrow a^d - 1 | a^n - 1
    Consider the geometric series of a^d :
    \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 a^d-1 divides 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 <br />
\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.<br />
(as Moo points out) thus <br />
\left( {a^{\left( {m,n} \right)}  - 1} \right)\left| {\left( {a^n  - 1,a^m  - 1} \right)} \right.<br />
(1)

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

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

    So every common divisor divides <br />
a^{\left( {n,m} \right)}  - 1<br />
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: December 23rd 2008, 01:27 PM
  2. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  3. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  4. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum