# Congruence by L.C.M

Determine the number of **ordered pairs** of positive integers such that their least common multiple

- 9 August, 2012 -
- Article, Math Problems -
- Tags : 104 problems, number theory, titu
- 0 Comments

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 .