2. a) For which natural numbers $n$, do there exist natural numbers $x$ and $y$ such that

$$
\text { LCM }(x, y)=n!; \quad \text { GCD }(x, y)=2009
$$

b) Determine the number of pairs $(x, y)$ such that

$$
\text { LCM }(x, y)=41!; \text { GCD }(x, y)=2009 ; x \leq y
$$
Solution. a) From GCD $(x, y)=2009$ it follows that $x=2009 a$ and $y=2009 b$, where $a$ and $b$ are natural numbers such that GCD $(a, b)=1$.

From LCM $(x, y)=n!$ it follows that $2009 a b=n!$, or $7^{2} \cdot 41 a b=n!$. From the latter, it follows that $n \geq 41$. The condition is also sufficient since if $n \geq 41$, for $x=2009$ and $y=n!$ it holds that LCM $(x, y)=n!$ and GCD $(x, y)=2009$.

b) Let for the numbers $x$ and $y$ it holds that LCM $(x, y)=41!$; GCD $(x, y)=2009$; $x \leq y$. Then $x=2009 a ; y=2009 b ;$ GCD $(a, b)=1 ; a \leq b$ and $2009ab = 41!$, or $ab=\frac{40!}{7^{2}}$. Every prime divisor of $\frac{40!}{7^{2}}$ is a divisor of $a$, not a divisor of $b$, and vice versa. The number $\frac{40!}{7^{2}}$ has exactly 12 prime divisors $2,3,5,7,11,13,17,19,23,29,31$ and 37, and each of them is a divisor of either $a$ or $b$. The number of such pairs $(a, b)$ is $2^{12}$, but only half of them satisfy the condition $a<b$. Therefore, there are exactly $2^{11}=2048$ pairs $(x, y)$ that satisfy the given condition.