The user-friendly version of this content is available here.
The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.
This essential trains for: AMC-8, Math Kangaroo 7-8, AMC-10, Math Kangaroo 9-10.
We want to find the number of ordered pairs of natural numbers that have the same, given LCM.
Let N be the value of the given LCM and consider its prime factorization:
or, if the notation for the product is too difficult, use:
where all x are distinct primes and all a are positive integers.
We are looking for the number of possibilities to select the numbers P and Q such that:
Now assume that, in the prime factorization of P, the prime factor xi occurs with exponent j, where:
then in the prime factorization of Q the exponent of xi must be ai.
On the other hand, if exponent of xi in the prime factorization of Q is ai, then its exponent in the factorization of P can be any k such that:
This means that the number of pairs of exponents is:
Since the choices corresponding to different prime factors are independent, the total number of pairs P and Q is:
The least common multiple of two numbers is 675. How many such pairs of numbers are there?
Factor the least common multiple:
Let P and Q be such that:
If the factor 3 appears with an exponent of 1 or 2 in the prime factorization of P, then it must have an exponent of 1 in the factorization of Q. The following table shows only the pairs of powers of 3 that are possible (a total of 7):
For the powers of 3 there are 5 possible pairs:
Therefore the number of choices for P and Q is: