Trick 2.0
-
This post is deleted! -
[Originally posted in Discussions]
I was taught a trick for finding least common multiple that legitimately works for all numbers. The way you do this is you prime factorize. But with both numbers, starting from the smallest prime number there is. What this means is that when you prime factorize by two, you divide both numbers by two. If you can’t divide by two, you go to three and so on (or you can automatically go to a certain number if you know your divisibility rules). Then, after you can’t divide anymore by whole prime numbers, you multiply the prime factors and the numbers you ended up with after dividing by those prime numbers. For example, 180 and 4:
180 and 4 divided by 2 is 90 and 2
90 and 2 divided by 2 is 45 and 1
Multiply 2 times 2 times 45 times 1
LCM is 180
The only thing is I don’t know why this was rocks so if you can tell me that’d be nice.
-
That's very interesting, thank you for sharing! Your school teachers probably didn't teach you why exactly it works, so it may not be as intuitive as looking at all the prime factors. However, I do think this can be a fast method.
Here's a nice way to think about why this method works: Let's first change your method a tiny bit like so:
Find a prime factor p of one of the numbers.
Divide that number by p, and any other number that is divisible by p. Keep doing this until all the numbers are 1.
Multiply up all the primes you divided by!
So to find the LCM of 4, 6, 8:
I first divide anything divisible by 2 to get 2, 3, 4.
Then I divide anything divisible by 2 to get 1, 3, 2.
Then I divide anything divisible by 2 to get 1, 3, 1.
Then I divide anything divisible by 3 to get 1, 1, 1.
2 x 2 x 2 x 3 = 24
You can see that this is the same method, it just takes longer because it "keeps going", even after there are no more primes that divide any two of the numbers (in other words, after the numbers are pairwise relatively prime).
To see why this method works, let's look at one prime factor, say 2. Why does the method give us the biggest exponent of 2 out of all the numbers? (Remember that taking the biggest exponent of each prime is one way to find the LCM) It's because we keep taking out 2's until there are no more 2's, so the number with the most 2's "survives" the longest!
Let's look at that example again, but just looking at the 2's, and with the prime factorizations:
1 | 2^2, 2*3, 2^3
2 | 2, 3, 2^2
2^2 | 1, 3, 2
2^3 | 1, 3, 1
2^3*3 | 1, 1, 1
Notice how basically all the 2's from the 2^3 (biggest exponent of 2) got carried over to the LCM, and smaller exponents of 2 (like the 2^2) didn't really matter in the end. Effectively, the LCM only had to take 2's from the biggest exponent of 2. That's why in the end, the number we get for LCM is indeed the product of all the biggest exponents of the primes!
I hope that helped you understand this method. Happy learning!
-
[Originally posted in Discussions]
Actually, if you have too many numbers or numbers that don't have any common factors, it doesn't work very well. Sorry for that.
