Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By Idea

Math Help - Problem with GCD

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    US
    Posts
    37
    Thanks
    1

    Problem with GCD

    if gcd(n,m) = d then prove that gcd((a^n)-1,(a^m)-1)=(a^d)-1.

    Help would be very appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Problem with GCD

    Let d be an integer that divides both n and m. Then n = rd and m = sd for some pair of integers r,s. So,

    \begin{align*}a^n-1 & = a^{rd}-1 \\ & = (a^{rd} - a^{(r-1)d}) + (a^{(r-1)d} - a^{(r-2)d}) + \cdots (a^{2d}-a^d) + (a^d-a^0) \\ & = a^{(r-1)d}(a^d-a^0) + a^{(r-2)d}(a^d-a^0) + \cdots + a^d(a^d-a^0) + a^0(a^d-a^0) \\ & = (a^d - a^0)\sum_{k = 0}^{r-1}a^{kd}\end{align*}

    Similarly, a^m-1 = (a^d-1)\sum_{k=0}^{s-1}a^{kd}.

    So, (a^d-1) clearly divides both a^n-1 and a^m-1 for any common divisor of m,n. So, a^{\gcd(m,n)}-1 is a common divisor of both a^n-1 and a^m-1. All that is left is to show that any other common divisor of a^n-1 and a^m-1 must divide a^{\gcd(m,n)}-1
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    89
    Thanks
    41

    Re: Problem with GCD

    ..... to show that any other common divisor of a^n-1 and a^m-1 must divide a^{\gcd(m,n)}-1

    If u is such a divisor then a^n and a^m are each congruent to 1 (mod u)

    We need to show that a^d is congruent to 1 (mod u) where d=gcd(m,n)

    This follows from the fact that d is a linear combination of m and n

    For example, say there are positive integers x and y such that x m + d = y n then

    \left(a^m\right)^xa^d=\left(a^n\right)^y

    a^d=1 (\text{mod}  u)
    Last edited by Idea; November 16th 2013 at 08:37 AM.
    Thanks from johng
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2013
    From
    US
    Posts
    37
    Thanks
    1

    Re: Problem with GCD

    Thanks I've finally figured it out!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum