Why does the product of primes help us derive the HCF and LCM (PROOF)?

C

Cambridge101

New member
Joined
Dec 16, 2021
Messages
49
Hi there,

Just a question I would like fully answered. Often students are taught just to accept that expressing a positive integer as a product of its primes will mean you can find the HCF and the LCM, there is never really an explanation for why this is the case. Could someone explain?

Intuitively, I can see that when one larger integer is a multiple of the smaller integer - the smaller integer must be the HCF. Simply by knowing that the highest factor of an integer is always itself. Thus, if the larger integer is a multiple of the smaller number, by definition this means we can produce this larger integer, by multiplying the smaller integer by some other integer. Thus the smaller integer is a factor of the larger integer. Meaning it is the HCF for the pair of integers, because the smaller is the highest factor for itself. Likewise, it is intuitive to see that when we have two integers and one is a multiple of the other, the LCM is always the bigger integer. Because every numbers lowest multiple is itself. So if the larger integer is a multiple of the other and itself. This by definition must be the LCM.

But why does expressing an integer using only a combination of prime factor help us find the HCF and the LCM for other numbers.
 
Expressing both numbers as products of (powers of) primes seems natural because this expression is unique and "maximal", i.e., it cannot be expanded any further. You can think of primes as "atoms" in pre-particle physics.And once you have the representations as products of primes for both number computing there HCF and LCM is quite straightforward.

But you are right that that representation is not necessary for computing HCF and LCM. E.g. Euclidean algorithm does not require that decomposition to compute HCF (a.k.a. GCD, or GCF, or HCD).
 
Cambridge101 said:
why does expressing an integer using only a combination of prime factor help us find the HCF and the LCM for other numbers.
Click to expand...

One way to see the HCF and LCM that makes it fairly clear how prime factors fit in is the Venn diagram approach shown at the end of this page.
 
Cambridge101 said:
Hi there,

Just a question I would like fully answered. Often students are taught just to accept that expressing a positive integer as a product of its primes will mean you can find the HCF and the LCM, there is never really an explanation for why this is the case. Could someone explain?

Intuitively, I can see that when one larger integer is a multiple of the smaller integer - the smaller integer must be the HCF. Simply by knowing that the highest factor of an integer is always itself. Thus, if the larger integer is a multiple of the smaller number, by definition this means we can produce this larger integer, by multiplying the smaller integer by some other integer. Thus the smaller integer is a factor of the larger integer. Meaning it is the HCF for the pair of integers, because the smaller is the highest factor for itself. Likewise, it is intuitive to see that when we have two integers and one is a multiple of the other, the LCM is always the bigger integer. Because every numbers lowest multiple is itself. So if the larger integer is a multiple of the other and itself. This by definition must be the LCM.

But why does expressing an integer using only a combination of prime factor help us find the HCF and the LCM for other numbers.
Click to expand...
There is a method of calculating HCF of two numbers without actually finding prime factors - Euclid's algorithm. However for more than two numbers that method can become more burdensome and it does not help you to find LCM.
 
Subhotosh Khan said:
There is a method of calculating HCF of two numbers without actually finding prime factors - Euclid's algorithm. However for more than two numbers that method can become more burdensome and it does not help you to find LCM.
Click to expand...
Once you know HCF computing LCM is pretty straightforward, isn't it?
 
Thank you all for responding. I am still no certain on why finding the numbers product of primes helps us find the HCF and LCM. Can someone do a proof?
 
Cambridge101 said:
Thank you all for responding. I am still no certain on why finding the numbers product of primes helps us find the HCF and LCM. Can someone do a proof?
Click to expand...
If you are asking for a formal proof you have to specify a formal statement which you want to be proved.
 
Cambridge101 said:
Thank you all for responding. I am still no certain on why finding the numbers product of primes helps us find the HCF and LCM. Can someone do a proof?
Click to expand...
Did you follow the direction in response #3?
 
Cambridge101 said:
yes, it does not really explain why, just how...
Click to expand...
A list of prime factors of two composite numbers , and their products will provide EVERY factor of those numbers.

Can you prove that to yourself?
 
Cambridge101 said:
Thank you all for responding. I am still no certain on why finding the numbers product of primes helps us find the HCF and LCM. Can someone do a proof?
Click to expand...
It isn't clear what you are asking.

The prime factorization of the numbers helps because it is used in several methods.

The method itself is the explanation of why or how the factorization helps, unless what you are asking for is a proof that some particular process produces the HCF and the LCM. In that case, you need to show us the method you are asking about. Can you give an example of the method you have learned?
 
Here is my issue.

Why does expressing a number as a product of primes help us identify the HCF and LCM.

I can just list out the factors of a number and that clearly highlights the common factors and from there I can identify the HCF.

But, what I want to know, is why expressing two numbers as products of prime numbers, then finding common primes and uncommon primes can produce the HCF and LCM.

Take the number 20 and 15.

(excluding negative factors)
I know that by listing, the factors of 20 = 1,2,4,5,10,20
I know that by listing, the factors of 15 = 1,3,5,15
Thus, the HCF is 5.

But why does the prime method actually work, what is going on why does it work?
Can someone explain step by step why expressing a number as a product of its primes and how this leads us to the HCF and LCM?
 
Cambridge101 said:
I know that by listing, the factors of 20 = 1,2,4,5,10,20
I know that by listing, the factors of 15 = 1,3,5,15
Thus, the HCF is 5.
Click to expand...
From your example:
the list of factors for 20 can be further broken down into primes: [imath]1,2,2^2,5,2*5,2^2*5[/imath]
the list of factors of 15 can be further broken down into primes:[imath]1,3,5,3*5[/imath]
As you can see, only the stand-alone 5 is the highest factor that is common in both. Thus the HCF is 5.
 
BigBeachBananas said:
From your example:
the list of factors for 20 can be further broken down into primes: [imath]1,2,2^2,5,2*5,2^2*5[/imath]
the list of factors of 15 can be further broken down into primes:[imath]1,3,5,3*5[/imath]
As you can see, only the stand-alone 5 is the highest factor that is common in both. Thus the HCF is 5.
Click to expand...
Ok, but why does writing the factors as a product of primes produce the HCF. Are you saying that because you can write the factors of 15 and 20 as their prime products, these primes must also be factors of the original numbers?

If so, why is this?
 
Cambridge101 said:
Ok, but why does writing the factors as a product of primes produce the HCF. Are you saying that because you can write the factors of 15 and 20 as their prime products, these primes must also be factors of the original numbers?

If so, why is this?
Click to expand...
As previously mentioned by Blamocur in post#2: "When you're expressing numbers as products of primes..., the number cannot be expanded any further. You can think of primes as "atoms". Meaning, integers are products of primes (literally and figuratively) as your car is a product of the nuts and bolts. When we're expressing the integer in primes (aka prime factorization), we're essentially breaking it down to the most basic components. Once you break the numbers 20 and 15, we can easily identify what is common and highest in both numbers.

Maybe an analogy would help. Let's say you're wondering how a BMW vs. Mercedes was built. From the outside, they look different (as 20 looks different than 15). But you know they're both cars (as 20 and 15 are integers), so they probably have similar parts. So you decided to break down the BMW and the Mercedes (as you're expressing 20 and 15 in primes). You found that the BMW was built with 1 type A bolt and 5 type B bolts, and 10 type C bolts. Whereas the Mercedes was built with 1 type A bolt, and 5 type B bolt, and 0 type C bolt. Now, you've identified both cars used type A and type B bolts (common), but type B used 5 bolts instead of 1 (highest). Hence the word Highest Common Factor.
 
Cambridge101 said:
Here is my issue.

Why does expressing a number as a product of primes help us identify the HCF and LCM.

I can just list out the factors of a number and that clearly highlights the common factors and from there I can identify the HCF.

But, what I want to know, is why expressing two numbers as products of prime numbers, then finding common primes and uncommon primes can produce the HCF and LCM.

Take the number 20 and 15.

(excluding negative factors)
I know that by listing, the factors of 20 = 1,2,4,5,10,20
I know that by listing, the factors of 15 = 1,3,5,15
Thus, the HCF is 5.

But why does the prime method actually work, what is going on why does it work?
Can someone explain step by step why expressing a number as a product of its primes and how this leads us to the HCF and LCM?
Click to expand...
Cambridge101 said:
Ok, but why does writing the factors as a product of primes produce the HCF. Are you saying that because you can write the factors of 15 and 20 as their prime products, these primes must also be factors of the original numbers?

If so, why is this?
Click to expand...

You still haven't shown a specific method using prime factors that you have seen, so perhaps you have only heard that they can be used, and don't know how it works. What you show is one of several methods that don't use prime factors. It is not just writing factors that gives the HCF, but what you do with those factors.

So let's look at an example, using one version of the method. Take the numbers 24 and 30, which factor as [imath]24=2^3\cdot 3[/imath] and [imath]30=2\cdot 3\cdot 5[/imath].

First, consider the HCF. We want to find the biggest number that is a factor (divisor) of both numbers. To be a divisor of 24 it must consist only of prime factors of 24, and nothing else. For instance, if 7 were a divisor of the number we pick, then any multiple of it would also have 7 as a factor, which isn't true of 24. And if it had 3 as a factor twice (making it a multiple of 9), then 24 couldn't be a multiple of it.

So our number must consist of no more than three 2's, and no more than one 3. Take that as a first try.

But our number also has to be a divisor of 30, so it can contain no more than one each of 2, 3, and 5.

So we have to reduce the number of 2's, making it one 2 times one 3, or [imath]6=2\cdot 3[/imath]. That's the HCF.

Do you see how knowing the prime factorization helped?

In general, the method is to use each prime factor that is in each number, and only the fewest times it appears in either number. So if we have bigger numbers (harder to work with by just listing factors), such as [imath]2^43^57^2 = 190,512[/imath] and [imath]2^25^37^4 = 30,012,500[/imath], we know quickly that the HCF is [imath]2^27^2 = 196[/imath].

I'll stop there for the moment and leave the LCM for later. I need to see whether what I am doing is the sort of thing you want.
 
You must log in or register to reply here.
Top