Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Plato

Thread: HCF of a and b

  1. #1
    Member
    Joined
    May 2010
    Posts
    100

    HCF of a and b

    Ok, i am stuck on a problem...

    I have been investigating HCF of (a,b) and noticed that a+b never seems to be a factor of the HCF (a,b).
    I am not sure how i can go about proving this?

    So for example, pick 2 & 3 : HCF =6 but 2+3 =5 and 5 is not a factor of 6.
    This is easy to prove when the HCF (a,b) = a*b but this is not always the case?
    Is it a proof by considering different cases?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,360
    Thanks
    2680
    Awards
    1

    Re: HCF of a and b

    Quote Originally Posted by rodders View Post
    I have been investigating HCF of (a,b) and noticed that a+b never seems to be a factor of the HCF (a,b).
    I am not sure how i can go about proving this?
    Well at least you could use the correct nomenclature.
    $\text{LCM}(a,b)$ is least common multiple. $\text{GCF}(a,b)$ is greatest common factor.
    Please check your text material to see if it gives a different set of definitions.
    Thanks from rodders
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2010
    Posts
    100

    Re: HCF of a and b

    Quote Originally Posted by Plato View Post
    Well at least you could use the correct nomenclature.
    $\text{LCM}(a,b)$ is least common multiple. $\text{GCF}(a,b)$ is greatest common factor.
    Please check your text material to see if it gives a different set of definitions.
    Apologies... Confused my own thinking and lost sight of what I mean!

    I will correct above if I can!
    I mean the take a, b , then why is a+b never a factor of the LCM (a,b)
    Last edited by rodders; Oct 9th 2016 at 04:15 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    717
    Thanks
    329

    Re: HCF of a and b

    First we prove the following fact (all positive integers)

    Fact. If a+b divides ab then gcd(a,b)>1

    If ab=m(a+b) then

    (b-m)(a+b)=b^2 and (a-m)(a+b)=a^2

    since a+b>1 consider a prime p that divides a+b

    p divides a and b therefore gcd(a,b)>1

    Now suppose lcm(a,b)=m(a+b)

    multiply both sides by gcd(a,b) to get

    ab=m(a+b)gcd(a,b)

    set c=a/gcd(a,b) and d=b/gcd(a,b)

    we get that cd=m(c+d) yet gcd(c,d)=1 contradicting the Fact
    Follow Math Help Forum on Facebook and Google+

Search tags for this page


/mathhelpforum @mathhelpforum