Results 1 to 3 of 3

Math Help - I need help finishing a gcd proof

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

    I need help finishing a gcd proof

    the question was to prove:
    if m and n are positive integers and gcd(m, n) = d, then gcd(2n - 1, 2m - 1) = 2d - 1.

    my approach was the following:

    given gdc(m,n) = d, the d|m and d|n also m = dp and n = dq for some integers p and q.
    so, (2n - 1, 2m - 1) = (2dq - 1, 2dp - 1)
    2dq - 1 = 2d - 1(2d(q-1) + 2d(q-2) +...+ 2d + 1) = (2d - 1)(s) for some integer s.
    2dp - 1 = 2d - 1(2d(p-1) + 2d(p-2) +...+ 2d + 1) = (2d - 1)(t) for some integer t.

    so (2d - 1) is a divisor of (2n - 1, 2m - 1), however I do not know how to show that it is the gcd(2n - 1, 2m - 1) or how to show that
    gcd(s,t) = 1.

    my instructor suggested proof by induction showing true for m + n < s, then true for m + n = s. I can not see how to start the proof
    using his suggestion. any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,664
    Thanks
    606

    Re: I need help finishing a gcd proof

    Hey bskcase98.

    If something is a greatest divisor (let alone a greatest common divisor), then it means that all divisors must be less than that divisor. In other words if you have n and the greatest divisor of n is a then if n = ab then b <= a. From this can you show that this holds?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: I need help finishing a gcd proof

    You've proven that, if d = gcd(a,b), then (2^d - 1) divides the gcd((2^a - 1), (2^b-1)).

    If you could prove that gcd((2^a - 1), (2^b-1)) divides (2^d - 1), then you'd be done, since they'd then be equal.

    Recall in a previous thread of yours called "need help with an Eucledian algorthim and gcd involving factorials and large exponets", I gave a long derivation? In there I wrote:
    "Proposition: If d divides (b^y - 1) and d divides (b^y - 1), then d divides (b^{gcd(x, y)} - 1). Rather than work out a proof, I'll run through it step by step for this problem."
    Well, now that proposition is exactly what you need. Switching the labelling back to the current problem, you'd be done if you could prove:

    Lemma: If c divides (2^a - 1) and c divides (2^b - 1), then c divides (2^{gcd(a, b)} - 1).

    If you can prove that Lemma, then, since c = gcd((2^a - 1), (2^b-1)) divides both (2^a - 1) and (2^b - 1), it would follow that

    c = gcd((2^a - 1), (2^b-1)) divides (2^{gcd(a, b)} - 1).

    And since you already have shown that (2^{gcd(a,b)} - 1) divides the gcd((2^a - 1), (2^b-1)), you'd then be done.

    That insane calculation I did in that other problem lays out - perhaps - the way for you to prove the above Lemma.

    By the way, that insane calculation is, I believe, called Euclid's Algorithm for finding the gcd.

    Just a thought. Good luck.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help finishing of a question
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 19th 2010, 07:01 AM
  2. Help finishing a proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 21st 2009, 09:33 PM
  3. I need help finishing this problem.
    Posted in the Calculus Forum
    Replies: 8
    Last Post: July 29th 2009, 01:54 PM
  4. Replies: 2
    Last Post: October 1st 2008, 12:32 PM
  5. [SOLVED] HELP! I need help finishing this problem!
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: February 12th 2008, 08:12 PM

Search Tags


/mathhelpforum @mathhelpforum