# Thread: HCF of a and b

1. ## 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?

2. ## Re: HCF of a and b

Originally Posted by rodders
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.

3. ## Re: HCF of a and b

Originally Posted by Plato
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)

4. ## 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

,

,

,

,

,

,

# waht is the hcf of A& B

Click on a term to search for related topics.