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
    166

    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,743
    Thanks
    2814
    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
    166

    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
    820
    Thanks
    375

    Re: HCF of a and b

    First we prove the following fact (all positive integers)

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

    If $\displaystyle ab=m(a+b)$ then

    $\displaystyle (b-m)(a+b)=b^2$ and $\displaystyle (a-m)(a+b)=a^2$

    since $\displaystyle a+b>1$ consider a prime $\displaystyle p$ that divides $\displaystyle a+b$

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

    Now suppose $\displaystyle lcm(a,b)=m(a+b)$

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

    $\displaystyle ab=m(a+b)gcd(a,b)$

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

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

Search tags for this page


/mathhelpforum @mathhelpforum