Least common multiple equation

Question

How many natural solutions does this equation have and why?
$$\operatorname*{lcm}(201, 209) = \operatorname*{lcm}(x, y)$$

Answer 1

Hint. Observe that $201=3\cdot 67$ and $209=11\cdot 19$ are decompositions into prime factors.

Answer 2

We want natural numbers $x,y$ such that $$\operatorname{lcm}(x,y)=\operatorname{lcm}(201,209)=\operatorname{lcm}(3\cdot67,\ 11\cdot19)=3\cdot11\cdot19\cdot67=42009.$$ Let $P=\{3,11,19,67]\}.$ Ssolutions are given by $$x=\prod_{p\in X}p,\quad y\in\prod_{p\in Y}p$$ where $$X,Y\subseteq P,\quad X\cup Y=P.$$ The number of solutions with $|X|=k$ is $\binom4k2^k,$ so the total number of solutions is $$\sum_{k=0}^4\binom4k2^k=(1+2)^4=3^4=\boxed{81}.$$

Alternatively, solutions are given by $$x=3^{\alpha_1}\cdot11^{\alpha_2}\cdot19^{\alpha_3}\cdot67^{\alpha_4},\quad y=3^{\beta_1}\cdot11^{\beta_2}\cdot19^{\beta_3}\cdot67^{\beta_4}$$ where $$\max(\alpha_i,\beta_i)=1\text{ for each }i,$$ that is, each $(\alpha_i,\beta_i)$ is either $(0,1)$ or $(1,0$ or $(1,1),$ so the number of solutions is $3^4=\boxed{81}.$

More generally, if $$N=p_1^{\varepsilon_1}p_2^{\varepsilon_2}\cdots p_m^{\varepsilon_m}$$ where $p_1,p_2,\dots,p_m$ are distinct primes and $\varepsilon_1,\varepsilon_2,\dots,\varepsilon_m$ are nonnegative integers, the number of natural solutions of the equation $$\operatorname{lcm}(x,y)=N$$ is $$(2\varepsilon_1+1)(2\varepsilon_2+1)\cdots(2\varepsilon_m+1).$$

Answer 3

201 = 3x67 and 209=11x19.

So to have lcm (a,b)= 3x67x11x19, each of those factors must either i) be a factor of a, ii) be a factor b or iii) be a factor of both a and b. (And a and b can't have any other factors). That's three options for 4 factors so there are $3^4=81$ possible pairs.

They are from 0000 to 2222:

0000:(3x11x19x67,1)

0001:(11x19x67,,3)

0002:(3x11x19x67,3)

0010:(3x19x67,11)

0011:(19x67,3x11)

0012:(3x19x67,3x11)

0020:(3x11x19x67,11)

0021:(11x19x67,3x11)

0022:(3x11x19x67,3x11)

etc.

the last to first digits represent the factors 3,11,19 and 16 and 0 mean the factor is a factor of a; 1 means it's a factor of b; and 2 means it's a factor of both:

So 1201 means 3 is a factor of b, 11 is a factor of a, 19 is a factor of both, and 67 is a factor of a. So the pair is (11x19x67,3x19).