Results 1 to 9 of 9

Math Help - Fundamental Theorem of Arithmetic

  1. #1
    Newbie
    Joined
    Feb 2007
    Posts
    18

    Fundamental Theorem of Arithmetic

    I solve this problem but I did not get the right solition.

    Show that if a and b are positive integers, then (a,b)=(a+b,[a,b])

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jmc1979 View Post
    I solve this problem but I did not get the right solition.

    Show that if a and b are positive integers, then (a,b)=(a+b,[a,b])

    Thank you!
    What does that mean?
    (a,b) probably means gcd(a,b).

    But what does [a,b] mean?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,659
    Thanks
    1616
    Awards
    1
    I suspect the problem is: gcd(a,b)=gcd(a+b, lcm(a,b)).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2007
    Posts
    18

    Least common multiple

    [a,b] means the Least Common Multiple

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2007
    Posts
    18

    You are correct

    Plato, you are correct!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,659
    Thanks
    1616
    Awards
    1
    Use the fundamental to write both a and b in prime factor form.
    Note that gcd(a,b) is a divisor of a+b. Moreover, ab=gcd(a,b)lcm(a,b).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2007
    Posts
    18

    Thanx

    Thank you Plato!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Here is an outline of the proof.

    You do not need to use the fundamental theorem here.

    We need to show.

    gcd(a+b,lcm(a,b))=gcd(a,d)

    Iff,

    gcd(a+b,ab/d)=d where d=gcd(a,b)

    Iff,

    gcd(ad+bd,ab)=d^2

    Now you can imagine why that is true.

    Look d^2 divides ad and bd.
    And d^2 divides ab.

    Now argue by contradiction to complete the proof.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Feb 2007
    Posts
    18

    One solution but not acepted

    This is one solution I found:

    Show that if a and b are positive integers then gcd(a,b)=gcd(a+b, lcm(a,b)).

    Solution: Let p be a prime that divides a or b. Then p divides a+b and [a,b]. Hence p divides both sides of the equation. Define s,t by p^s || a, p^t || b, say that a=xp^s and b=yp^t. Without loss of generality, suppose st. Then a+b = p^s (x + p^(t-s)), so p^s || a+b. Also, p^(max(s,t)) || lcm(a,b). But max(s,t)=t, so p^t || lcm(a,b). Therefore p^(min(s,t)) || gcd(a+b,lcm(a,b)). But min(s,t)=s, so the same power of p divides both sides of the equation. Therefore the two sides must be equal.

    This solution but is not accepted by the professor because he states that the first two sentences are not enough explanation for this exercise or with another solution with explanation. Can anyone help me with this exercise with an explanation? Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof Using Fundamental Thm of Arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2011, 03:52 PM
  2. Fundamental Theorem of Arithmetic
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 15th 2010, 04:31 PM
  3. Fundamental Theorem of Arithmetic...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 10th 2009, 03:44 PM
  4. Fundamental Theorem of Arithmetic Help
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 24th 2007, 03:41 PM

Search Tags


/mathhelpforum @mathhelpforum