Results 1 to 7 of 7

Math Help - Help with elem. proof

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    168

    Help with elem. proof

    Prove that if (a,b)=[a,b] then a=b.

    I'm not sure how to start this one. I thought maybe using the fact that
    (a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

    Any hints?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Please clarify your notation. Is (a,b) an ordered pair? And what is [a,b]?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    168
    Quote Originally Posted by DrSteve View Post
    Please clarify your notation. Is (a,b) an ordered pair? And what is [a,b]?
    Sorry, should have done that.
    (a,b)=gcd(a,b)
    [a,b]=lcm(a,b)

    So basically, if two numbers have the same gcd and lcm, then they must be equal. But how can I prove that?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by paupsers View Post
    Prove that if (a,b)=[a,b] then a=b.

    I'm not sure how to start this one. I thought maybe using the fact that
    (a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

    Any hints?
    Given  \displaystyle a=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} and  \displaystyle b=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}

    Then  \displaystyle (a,b) = p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_k^{\min(a_k,b_k)} and  \displaystyle [a,b] = p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_k^{\max(a_k,b_k)}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Aha - that makes more sense!

    I can think of one way to do it using the fundamental theorem of arithmetic. I'll give you the main idea, and see if you can write it up rigorously:

    a and b can each be factored uniquely as a product of primes. You get the gcd by taking the lowest power of each prime that appears. You get the lcm by taking the highest power of each prime that appears. If the gcd and lcm are equal, then the lowest power of each prime equals the highest power of each prime. So a and b have the same prime factorizations, and thus they are the same.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by paupsers View Post
    Prove that if (a,b)=[a,b] then a=b.

    I'm not sure how to start this one. I thought maybe using the fact that
    (a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

    Any hints?
    I assume that a and b are nonnegative.

    We have (a,b)\leq a and b\leq[a,b]. From (a,b)=[a,b] it follows that b\leq a.
    Similiarly, write (a,b)\leq b and a\leq[a,b]; so a\leq b. The two inequalities give a=b .

    For any integers a and b the result is that a=\pm b. (Using the abolute values...)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    168
    Thanks! I actually wasn't able to use the Fundamental Theorem of Arithmetic (since we don't "know" that yet) but your proof was simple and makes perfect sense!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with Elem. Linear Algebra Proof?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 29th 2009, 05:53 PM
  2. Elem. proof help?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: July 7th 2009, 12:33 PM
  3. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 9th 2009, 01:50 AM
  4. Elem Number Theory - gcd theorem in proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 2nd 2008, 11:16 AM
  5. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum