k is a positive integer and 225 and 216 are both divisors of k. if k = 2^{a} 3^{b} 5^{c} where a,b, and c are positive integers, what is the least possible value of a + b + c?
Hard question. Any guesses?
( latex kept generating errors when i tried variable superscript)
LCM 225 216 - Wolfram|Alpha
according to the text the answer is 8
the general idea is this:
suppose
where each is a different prime (if a prime does not occur in the factorization of one of m or n, we can take that exponent to be 0),
then
where .
it's easier to explain this with an example:
suppose we have 70 and 90 and we want to find the smallest number that is divisible by both. first, we factor 70 and 90 into primes:
70 = (2)(5)(7)
90 = (2)(3^2)(5)
the primes in this case are 2,3,5 and 7. re-writing both numbers in terms of these primes:
70 = (2^1)(3^0)(5^1)(7^1)
90 = (2^1)(3^2)(5^1)(7^0)
so the least common multiple will be of the form:
(2^a)(3^b)(5^c)(7^d) where:
a = max(1,1), b = max(0,2), c = max(1,1), d = max(1,0).
so a = 1, b = 2, c = 1, d = 1 (all we're doing is picking the "biggest power" of any prime we find in the prime factorizations).
so lcm(70,90) = (2^1)(3^2)(5^1)(7^1) = (2)(9)(5)(7) = 630.
there is also another way of doing this, which is to find the greatest common divisor (factor) of 70 and 90 (which we can do 2 ways, one of which is to pick the "smallest power" of any prime which occurs in both factorizations, or the following way):
90 = 1(70) + 20
70 = 3(20) + 10 <--- this remainder is the gcd
20 = 2(10) + 0 <---when we get 0, we go "back 1 step".
now that we know gcd(70,90) = 10, we can find the lcm like this:
lcm(70,90) = (70)(90)/gcd(70,90) = 6300/10 = 630.
so let's use this second method to find lcm(216,225).
first, we find gcd(216,225):
225 = (1)(216) + 9
216 = (24)(9) + 0 <-- go back one step, the gcd is 9.
so lcm(216,225) = (216)(225)/9 = 48,600/9 = 5,400
now we factor 5,400 into primes:
5,400 = (8)(675) = (8)(27)(25) = (2^3)(3^3)(5^2).
Zarathustra, i know, and you know, that the integers are a unique factorization domain. most people never see a proof of this fact until college (if ever).
but most people are willing to "take this on faith", and factoring into primes is usually part and parcel of how people learn to "reduce fractions".
so my post is not about why you can always do this (which is rather a deep subject), but merely a constructive algorithm to find the least common multiple
assuming one doesn't question that this can always be done.
and, it sounds complicated, because it IS complicated. numbers can be really, really big, with LOTS of prime factors, and finding a least common multiple,
or even a greatest common factor, can be a lot of arithmetic. even this example, where the primes involved are all less than 10,
involves doing arithmetic with numbers that are 4-5 figures, and could easily result in error if one had to solve it without the use of a calculator.