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: Example

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: 