Least common multiple equation How many natural solutions does this equation have and why?
$$\operatorname*{lcm}(201, 209) = \operatorname*{lcm}(x, y)$$
 A: 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).$$
A: Hint. Observe that $201=3\cdot 67$ and $209=11\cdot 19$ are decompositions into prime factors.
A: 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).
