Results 1 to 4 of 4

Math Help - On GCDs and power's of 2

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    On GCDs and power's of 2

    This is based on a earlier post on this forum only. Following lemma was used to solve a problem posted earlier - http://www.mathhelpforum.com/math-he...rs-155363.html

    (m,n) =1 \implies (2^m-1,2^n-1) = 1

    My question how do I prove this?

    I have made an attempt but am stuck at this -

    Given - Let m,n be any +ve integers. If a proposition is true for m and n then following holds true
    1. proposition is true for (m+n)
    2. proposition is true for (m-n), provided (m-n)>0

    Claim - Proposition is true for all
    am + bn, provided (am + bn) > 0, where a,b are any intergers (not necessarily >0)

    How do I prove my claim? Some sort of induction?

    Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Please ignore - I got it.

    Here is an outline of my approach

    I proved that if k|2^m-1 and k|2^n-1 => k|2^{m+n}-1 and k|2^{m-n}-1
    Thus k|2^{am+bn} - 1 => k|2-1

    Thanks
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    7
    Can you please explain why k|2^am+bn - 1 and the next step (=> k|2-1). I already know why k|2^m+n -1 and why k|2^m-n -1 but I don't know what to do next.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Hint -

    1. If k|2^m+n -1 and k|2^m - 1 then k|2^(2m)+n -1 and so on.....
    2. am + bn = 1 so k|2^am+bn - 1 => k|2-1 => k = 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. GCDs and LCMs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 16th 2011, 08:45 PM
  2. GCDs of polynomials
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 29th 2010, 08:38 PM
  3. Proofs USING GCDs
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2009, 09:35 PM
  4. Exponents power to a power
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 27th 2009, 01:39 AM
  5. gcds
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 6th 2008, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum