Results 1 to 10 of 10

Math Help - Two consecutive Z are relatively prime iff. their LCM=GCD.

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Two positive Z are relatively prime iff. their LCM=ab

    Two \mathbb{Z}^+ are relatively prime iff. their LCM=ab.

    LCM(a,b)=\frac{ab}{GCD(a,b)}

    1. Assume a and b are relatively prime.
    GCD(a,b)=1

    LCM(a,b)=\frac{ab}{1}=ab

    2. Assume LCM=ab.
    LCM(a,b)=\frac{ab}{GCD(a,b)}\rightarrow GCD(a,b)=\frac{ab}{LCM(a,b)} \ \mbox{but since the LCM=ab} \ GCD(a,b)=1
    Last edited by dwsmith; June 20th 2010 at 05:03 PM. Reason: Wrong word
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    Two consecutive \mathbb{Z} are relatively prime iff. their LCM=GCD.

    LCM(a,b)=\frac{ab}{GCD(a,b)}

    1. Assume a and b are relatively prime.
    GCD(a,b)=k\rightarrow k|a \ \mbox{and} \ k|b\rightarrow k|(\alpha a+\beta b)

    I am not sure if this going in the right direction.

    2. Assume LCM=GCD.
    Not sure how to go this direction.
    I don't understand the whole setup of this problem. Two consecutive integers are always relatively prime. And consider 3 and 4. Their LCM is 12 and their GCD is 1. Are you sure you copied it out right?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    I don't understand the whole setup of this problem. Two consecutive integers are always relatively prime. And consider 3 and 4. Their LCM is 12 and their GCD is 1. Are you sure you copied it out right?
    I edited the original post. I had consecutive integers on the brain.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    I edited the original post. I had consecutive integers on the brain.
    Hmm, I'm still not seeing it. My above example of 3 and 4 still applies... when two integers are relatively prime, their GCD is 1, and the only way to have LCM equal to 1 is if both integers are 1. Am I missing something?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    Hmm, I'm still not seeing it. My above example of 3 and 4 still applies... when two integers are relatively prime, their GCD is 1, and the only way to have LCM equal to 1 is if both integers are 1. Am I missing something?
    Ok I re-edited it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    Ok I re-edited it.
    Ohh okay it makes sense now.

    My first thought is to use prime factorisations. I think the most convenient notation for prime factorisation is to use an infinite product and allow exponents to equal 0. This has the added advantage that we don't have to treat 1 as a special case.

    a=p_1^{\alpha_1}p_2^{\alpha_2}\dots=\displaystyle\  prod_{i=1}^\infty p_i^{\alpha_i}

    b=p_1^{\beta_1}p_2^{\beta_2}\dots=\displaystyle\pr  od_{i=1}^\infty p_i^{\beta_i}

    where for simplicity we let p_1=2, p_2=3, p_3=5, \dots

    We have that

    \text{lcm}(a,b)=p_1^{\max(\alpha_1,\beta_1)}p_2^{\  max(\alpha_2,\beta_2)}\dots=\displaystyle \prod_{i=1}^\infty p_i^{\max(\alpha_i,\beta_i)}

    We also have that

    ab = \displaystyle \prod_{i=1}^\infty p_i^{\alpha_i+\beta_i}

    So we have \text{lcm}(a,b)=ab \iff \forall i\in\mathbb{Z},i>0:\max(\alpha_i,\beta_i)=\alpha_i  +\beta_i which is true if and only if either \alpha_i=0 or \beta_i=0, or both. Can you show how this last part is equivalent to a\ \text{and}\ b\ \text{are relatively prime}?

    (Fixed a small typo)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    Ohh okay it makes sense now.

    My first thought is to use prime factorisations. I think the most convenient notation for prime factorisation is to use an infinite product and allow exponents to equal 0. This has the added advantage that we don't have to treat 1 as a special case.

    a=p_1^{\alpha_1}p_2^{\alpha_2}\dots=\displaystyle\  prod_{i=1}^\infty p_i^{\alpha_i}

    b=p_1^{\beta_1}p_2^{\beta_2}\dots=\displaystyle\pr  od_{i=1}^\infty p_i^{\beta_i}
    I don't understand why we would say a and b are infinite products and if they are to the 0 power, wouldn't that make ever p then =1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    I don't understand why we would say a and b are infinite products and if they are to the 0 power, wouldn't that make ever p then =1
    Well consider the integer 126. The typical way to express the prime factorisation is

    126=2^1\cdot3^2\cdot7^1

    But if we instead write

    126=2^1\cdot3^2\cdot5^0\cdot7^1\cdot11^0\cdot13^0\  cdots

    this gives us flexibility when comparing the prime factorisations of two different integers, because we can just match up each corresponding index without having to use notation to indicate the highest non-zero index, etc.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    Well consider the integer 126. The typical way to express the prime factorisation is

    126=2^1\cdot3^2\cdot7^1

    But if we instead write

    126=2^1\cdot3^2\cdot5^0\cdot7^1\cdot11^0\cdot13^0\  cdots

    this gives us flexibility when comparing the prime factorisations of two different integers, because we can just match up each corresponding index without having to use notation to indicate the highest non-zero index, etc.
    I updated my first post with what I think my work. Can you let me know what you think? Thanks.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Well if we're allowed to use that \text{lcm}(a,b)=\displaystyle\frac{ab}{\gcd(a,b)} then the \Leftarrow direction also follows easily.

    Assume \text{lcm}(a,b)=ab

    Then \text{lcm}(a,b)=\displaystyle\frac{ab}{\gcd(a,b)}

    \Rightarrow ab=\displaystyle\frac{ab}{\gcd(a,b)}

    \Rightarrow \gcd(a,b)=1

    Edit: Ah, you just changed your first post and added another post saying you changed it. Looks good.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. 3 consecutive prime numbers.
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 10th 2010, 06:32 AM
  3. [SOLVED] Two consecutive numbers are relatively prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: June 20th 2010, 02:50 PM
  4. Consecutive integers/prime factorization problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 11th 2010, 06:52 AM
  5. Two Consecutive Odd Prime Numbers
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: November 6th 2008, 03:46 PM

/mathhelpforum @mathhelpforum