Add Me!Close Menu Navigation

Congruence by L.C.M

Determine the number of ordered pairs of positive integers (a,b) such that their least common multiple [a,b] = 2^35^711^{13}

Theorem: Given two numbers s and t such that their prime factorization are s = 2^{\alpha_2} \times 3^{\alpha_3} \times p_k^{\alpha_k} and t = 2^{\beta_2} \times 3^{\beta_3} \times p_k^{\beta_k}, then

    \[[s,t] = 2^{\max(\alpha_2, \beta_2)} \times 3^{\max(\alpha_3, \beta_3)} \times p_k^{\max(\alpha_k, \beta_k)}\]

This theorem comes naturally from the definition of the least common multiple as \inf M_s \cap M_t where M_k is the set of multiples of k.

In this case, we just need to find all pairs of integers such that \max(x_a, x_b) = 3, \max(y_a,y_b) = 7, \max(z_a,z_b) = 13 where a = 2^{x_a}5^{y_a}11^{z_a} and likewise for b.

For the case of finding all ordered pairs (x_a,x_b) such that \max(x_a,x_b) = 3, we see that the following pairs satisfies the constraints:

    \[(0,3),(1,3),(2,3),(3,3),(3,2),(3,1),(3,0)\]

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 (3,3) appears in both of these cases, we subtract one.

Generalizing this argument for any arbitrary pair \max(a,b) = k, there are a total of 2(k+1)-1 = 2k+1 ways of doing this. Hence, there are (2\times 3+1)(2\times 5+1)(2\times 13+1) = 7 \times 15 \times 27 = 2835 ordered pairs whose lcm is 2^35^711^{13}. \blacksquare

Posted By Lee

Woosh