Determine the number of ordered pairs of positive integers such that their least common multiple
Theorem: Given two numbers and such that their prime factorization are and , then
This theorem comes naturally from the definition of the least common multiple as where is the set of multiples of .
In this case, we just need to find all pairs of integers such that where and likewise for .
For the case of finding all ordered pairs such that , we see that the following pairs satisfies the constraints:
There are 4 ways of constructing pairs with a 3 in the first slot of the pair, and 4 ways of constructing pairs with a 3 in the second slot. However, because appears in both of these cases, we subtract one.
Generalizing this argument for any arbitrary pair , there are a total of ways of doing this. Hence, there are ordered pairs whose lcm is .