I want to understand intuitively why LCM(a,b)=ab/GCF(a,b)

[Juwane]

I want an intuitive understanding of why the lowest common multiple of two numbers is equal to the two numbers multiplied together, divided by the greatest common factor of the two numbers, i.e.,

LCM(a,b)=(a*b)/GCF(a,b)

I wish to know how this formula gives us the LCM of the two numbers.

 

[Hurkyl]

Focus on individual primes.

 

[statdad]

Consider a specific example (this is a good way to look at the "why" of a formula like this; once you see the workings in a particular case, you get a feel for the general case).

I'll use a = 84, b = 96. The prime factorizations of these are

<br /> \begin{align*}<br /> a &amp; = 2^2 \cdot 3\cdot 7 \\<br /> b &amp; = 2^5 \cdot 3<br /> \end{align*} <br />

It's easy to see that the LCM of these numbers is 2^5 \cdot 3 \cdot 7 and, further, that the GCF is 2^2 \cdot 3. Now

<br /> LCM(a,b) \times GCF(a,b) = \big(2^5 \cdot 3 \cdot 7\big) \times \big(2^2 \cdot 3\big) = \big(2^2 \cdot 3 \cdot 7\big) \times \big(2^5 \cdot 3\big) = a \times b<br />

or, to summarize

<br /> LCM(84,96) \times GCF(84,96) = 84 \times 96 \Rightarrow LCM(84,96) = \frac{84 \times 96}{GCF(84,96)}<br />

which gives your formula for this pair. If you are careful with your notation when you look
at prime factorizations for arbitrary choices, the same thing happens.

 

[Juwane]

I'll use a = 84, b = 96. The prime factorizations of these are

<br /> \begin{align*}<br /> a &amp; = 2^2 \cdot 3\cdot 7 \\<br /> b &amp; = 2^5 \cdot 3<br /> \end{align*} <br />

It's easy to see that the LCM of these numbers is 2^5 \cdot 3 \cdot 7 and, further, that the GCF is 2^2 \cdot 3.

Somehow it is not easy for me to see why the LCM of the two numbers is 2^5 \cdot 3 \cdot 7.

Can you please tell me how you can tell the LCM from the prime factors of the numbers?

Sorry for asking silly questions.

 

[Gerenuk]

Each integer has a set of prime factors. Now try to imagine what LCM and GCF represent.

Hint: One is the union set (http://en.wikipedia.org/wiki/Union_(set_theory)) and the other the intersection set (http://en.wikipedia.org/wiki/Intersection_(set_theory)) of these two sets of prime numbers.

 

[Juwane]

I really don't understand why LCM(a,b) \times GCF(a,b) = a \times b. I know it has to do with the definition of LCM and GCF, and I understand what an LCM and GCF is, but somehow I can't see why their product should be equal to the product of the numbers they are the LCM and GCF of.

 

[rasmhop]

As people have said before consider primes and prime factorizations. For instance for a prime p and integers c,d what is \text{lcm}(p^c,p^d) and \gcd(p^c,p^d). Can you generalize the formula to prime factorizations? (statdad's example should give you a hint that the answer is yes, and what it looks like).

 

[Juwane]

Here is an example from me:

Consider numbers 12 and 18.

Multiples of 12 are: 12, 24, 36, 48...
Multiples of 18 are: 18, 36, 54...

Clearly, the least common multiple is 36.

The factors of 12 are: 1, 2, 3, 4, 6, 12
The factors of 18 are: 1, 2, 3, 6, 9, 18

Clearly, the greatest common factor is 6.

What I want to ask is why LCM(12,18) \times GCF(12,18) = 36 \times 6 = 12 \times 18

 

[statdad]

Somehow it is not easy for me to see why the LCM of the two numbers is 2^5 \cdot 3 \cdot 7.

Can you please tell me how you can tell the LCM from the prime factors of the numbers?

Sorry for asking silly questions.

To get the LCM

* Write down each prime factor to the HIGHEST power it has in either factorization

To get the GCF

* Write down each prime factor to the LOWEST power it has in either factorization

 

[matticus]

in your example you have completely ignored prime factorization.

suppose we write a number as a list of exponents n=(e1,e2,e3,...) where only finitely many ei's are non-zero, and so that e1 is the exponent of 2, e2 is the exponent of 3, and en is the exponent of the nth prime.

in your example 12 = 2^2*3^1= (2,1,0,0,...) and 18 = 2^1*3^2= (1,2,0,0,...)

Now, to find the lcm we compare each position and choose the larger (or equal) exponent.
lcm(12,18) = (2,2,0,0,...) = 36
Similarly, to find the gcd we compare each position and choose the smaller (or equal) exponent.
gcd(12,18) = (1,1,0,0,...)= 6
Now 12*18 = (2,1,0,0,...)*(1,2,0,0,...)=(2+1,1+2,0,0,...)
When we multiply the lcm*gcd, we are still going to add the same exponents at the same position, the only difference could possibly be the order which they are added depending on which is larger. Since addition of integers is commutative, this does not matter.

Another example for clarification:

28 = 2^2*7^1 (2,0,0,1,0,0,...)
20 = 2^2*5^1 (2,0,1,0,0,...)
lcm(28,20) = (2,0,1,1,0,0,...)
gcd(28,20) = (2,0,0,0,...)
So each exponent from all primes in both numbers have been accounted for exactly once so the product lcm*gcd is the same as 28*20.

 

[Juwane]

Matticus, thank you for your explanation, but I'm looking for an easier explanation, one without prime factorization if possible.

I think LCM and GCF are exact opposites of each other--

smallest common multiple
greatest common factor

--except that they both have to do with commonness. If this is true, then I want to understand in the light of this fact.

 

[rasmhop]

I'm not sure if this explanation is easier, but it doesn't use prime factorization which you want to avoid for some reason.

If a' and b' are relatively prime then GCF(a',b') = 1 and LCM(a',b') = a'b'. To see the latter just note that otherwise LCM(a',b') = a'b'/k for some integer k, but then k is a common factor of a' and b'.
Also GCF(a'g,b'g)=g * GCF(a',b') and LCM(a'g,b'g) = g * LCM(a',b').

Now let g=GCF(a,b), then we can write a and b as:
a = a'g
b = b'g
for relatively prime integers a', b'. Then we have:

GCF(a,b)LCM(a,b) = GCF(a'g,b'g)LCM(a'g,b'g) = g^2 GCF(a',b')LCM(a',b') = a'b'g^2 = ab

 

[Juwane]

I guess I'll just memorize that LCM(a,b) \times GCF(a,b) = a \times b

 

[statdad]

Memorization of formulae won't get you far. You've had several very good explanations about why this relationship holds - and I submitted an explanation as well. Understanding the reasons things work as they do is entirely different than memorizing results, and without understanding you run the risk of applying results when they shouldn't be.

In short, sometimes 'understanding' requires some work on your part.

 

[Juwane]

Reading rasmhop's explanation, I now understand why LCM(a,b) \times GCF(a,b) = a \times b is true for relatively prime integers, but I still don't understand why it is true for integers with common factors and/or common multiples.