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:

equation

or, if the notation for the product is too difficult, use:

equation

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:

equation

Now assume that, in the prime factorization of P, the prime factor xi occurs with exponent j, where:

equation

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:

equation

This means that the number of pairs of exponents is:

equation

Since the choices corresponding to different prime factors are independent, the total number of pairs P and Q is:

equation

Example

The least common multiple of two numbers is 675. How many such pairs of numbers are there?

Factor the least common multiple:

equation

Let P and Q be such that:

equation

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

equation

equation

equation

equation

equation

equation

equation

equation

For the powers of 3 there are 5 possible pairs:

equation

equation

equation

equation

equation

equation

Therefore the number of choices for P and Q is:

equation