a)For which integers $n$ do there exist integers $(x,y): x\geq y$, $gcd(x,y)=1998$, and $ lcm(x,y)=n!$?
b) For which $n$ is the number of such pairs less than $1998$
My attempt:
$1998=2*3^3*37$.
So, for any $n\geq 37$, consider $x=n!$ and $y=1998$ to satisfy (a).
For any $n<37$, assume such a pair $(x,y)$ existed
Then $37|1998$, $1998|x$ and $x|n$!
So, $37|n!$, a contradiction
Now, we need the numbers for which number of such pairs is less than $1998$
As $(x,y)$ are symmetric it seems like as long as we can differentiate one from the other, we can switch them to satisfy $x\geq y$
Let us suppose $p_1=2,p_2=3,etc$ noting that $p_{12}=37$
Let $n!=p_1^{i_1}p_2^{i_2}...p_r^{i_r}$ where $p_r$ is the largest prime less than $n$
For any $n\geq 37$,
$i_1>1, i_2>3$
As both $x,y$ containg the powers $2^1*3^3$ by hypothesis, one of them must contain ALL the $i_1$ powers of $2$ and the other must contain ALL the $i_2$ powers of $3$, otherwise the $gcd(x,y)\not=1998$
The same is true for all the primes in the set ${5,7,11,13,17,19,23,29,31}$
WLOG let $x$ contain the powers of 2
Then for the powers of 3, there are two possibilities, they can divide either $x$ or $y$
Thus, by the time we reach $p_{11}=31$ there are $2^{10}=1024$ possibilities for $(x,y)$
For $37$ however there is only one factor in $37!$ which is contained in both $x$ and $y$, only one possibility
Same for $n=38,39,40$
For $n=41$ a new prime is introduced and the number of possibilities double again past $1998$
Thus, as per this logic the answer should be $n=37,38,39,40$
Am I correct? I am unable to find the solution anywhere
The problem in its original form is:
a) For which positive integers $n$ do there exist positive integers $x,y$ such that:
$lcm(x,y)=n!$ and $\gcd(x,y)=1998$
b) For which $n$ is the number of such pairs $x,y$ with $x \leq y$ less than $1998$?
Your answer for both parts are correct. Here is a more direct argument for (b):
Let $x=1998a,y=1998b, \gcd(a,b)=1$. Consider the case where $37 \leq n < 41$. Let $k=ab=\frac{n!}{1998}$. Clearly, the prime factors of $k$ are: $2,3,5,7,11,13,17,19,23,29,31$. Since $\gcd(a,b)=1$, if a prime factor of $k$ occurs in $a$, then it cannot occur in $b$, and vice versa. Hence, there are $2^{11}=2048$ ways to choose the prime factors to occur in either $a$ or $b$. However, only half of these choices will satisfy the requirement that $a \leq b$; hence, for $37 \leq n <41$, there will be a total of $1024 < 1998$ pairs.
On the other hand, if $n \geq 41$, which is a prime, then there would be at least $12$ prime factors of $k$, with the twelfth prime factor being $41$. But this means we would have at least $2^{12}=4096$ ways to choose the prime factors of $k$ to occur in either $a$ or $b$. But even after accounting for symmetry such that $a \leq b$, there would still be at least $\frac{4096}{2}=2048 > 1998$ number of such pairs. Hence, we conclude that $37 \leq n < 41$.