Math Is Fun Forum

paulb203

Member

Registered: 2023-02-24

Posts: 261

Finding the HCF of two numbers

Why does the prime factors/Venn diagram system work for this?

Example.
Find the HCF of 42 and 56
Prime factors of 42; 2,3,7.
Prime factors of 56; 2,2,2,7.

The intersection of the Venn diagram contains 2 and 7, so the HCF is 14, which checks out when you use the simple method of listing all factors of 42 and 56 and look for the HCF that way.

But why does this work?

All I can glean from the 2 and the 7 in the intersection (imagining I didn’t know what the 2 original numbers were, that I didn’t know they were 42 and 56) is that both numbers must be at least 14; and that one of them must be at least 28.
They must be at least 14 because both have 2 and 7 as factors.
One must be at least 28 because its circle in the diagram must contain at least one other prime factor (beyond the intersection) and the lowest of these is 2.

But I can’t work out why the 2 and the 7 produce the HCF.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,524

Re: Finding the HCF of two numbers

To make a Venn diagram, draw one circle for each number. Put the prime factors inside the circles so that common primes are in the intersecting part of the diagram.

The union gives the LCM.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Jai Ganesh

Administrator

Registered: 2005-06-28

Posts: 47,703

Re: Finding the HCF of two numbers

Hi paulb203,

See the links. (GCD is Greatest Common Divisor; HCF are Highest Common Factor; GCF is Greatest Common Factor : All the three are the same).

Greatest Common Divisor.

Coprime definition.

Coprime Explained.

Coprime Calculator.

---

It appears to me that if one wants to make progress in mathematics, one should study the masters and not the pupils. - Niels Henrik Abel.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

paulb203

Member

Registered: 2023-02-24

Posts: 261

Re: Finding the HCF of two numbers

To make a Venn diagram, draw one circle for each number. Put the prime factors inside the circles so that common primes are in the intersecting part of the diagram.

https://i.imgur.com/O2ganzy.gif

The union gives the LCM.

Bob

Thanks, Bob.
But why does intersection give us the products of the HCF? I get how to obtain the HCF from that method, but I don't know why it works.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,524

Re: Finding the HCF of two numbers

It's all in the name. HCF is highest common factor.  The common factors must be in the intersection because that's what the intersection means.  We want the highest so multiply them together.

Splitting the factors into their primes components helps us to identify the common ones.  You could put {1,2,3,6,7,14,21,42} all in one circle and {1,2,4,7,8,14,28,56} in the other, and then you could spot that 14 is the highest in both sets but it's a lot more work.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

paulb203

Member

Registered: 2023-02-24

Posts: 261

Re: Finding the HCF of two numbers

It's all in the name. HCF is highest common factor.  The common factors must be in the intersection because that's what the intersection means.  We want the highest so multiply them together.

Splitting the factors into their primes components helps us to identify the common ones.  You could put {1,2,3,6,7,14,21,42} all in one circle and {1,2,4,7,8,14,28,56} in the other, and then you could spot that 14 is the highest in both sets but it's a lot more work.

Bob

Thanks, Bob.

I got that the common factors were in the intersection. It was the bit where multiplying them together produced the highest common factor that I didn't get. I think the penny is starting to drop now.