For which $n$ is the number of such pairs $x,y$ with $\operatorname{lcm}(x,y)=n!$,$\gcd{(x,y)}=1998$

Question

For which $n$ is the number of such pairs $x,y$ with $x\le y$, less than $1998?$,and $$\operatorname{lcm}(x,y)=n!~~~~~~~~~~~~~~\gcd{(x,y)}=1998?$$

I known $1998=2\times 3^3\times 37$,so if $n\ge 37$,then $37|[x,y]$,Any help would be appreciated.

Answer 1

Note that a natural number $x$ is uniquely determined by its prime factorization, i.e., by the sequence of exponents $v_p(x)$ with which all primes $p$ occur in $x$. On the other hand, any such sequence of exponents that is $=0$ for almost all $p$, determines a natural number.

The exponent $v_p(n!)$ of $p$ in $n!$ is well-known to be given by $$\tag1v_p(n!)=\lfloor \frac np\rfloor +\lfloor \frac n{p^2}\rfloor +\lfloor \frac n{p^3}\rfloor +\ldots.$$

A pair $(x,y)$ of natural numbers has the properties $\gcd(x,y)=1998$ and $\operatorname{lcm}(x,y)\mid n!$ if and only if $\min\{v_p(x),v_p(y)\}=v_p(1998)$ and $\max\{v_p(x),v_p(y)\}=v_p(n!)$ vor all primes $p$. In particular, no such pairs exist at all (and hence $n$ is a solution to the problem) if for some $p$ we have $v_p(1998)>v_p(n!)$. From $v_{37}(1998)=1$, we conclude

If $n<37$, then $n$ is a solution.

Assume now that $n\ge 37$. Then $v_p(n!)\ge v_p(1998)$ for all $p$ (namely $v_2(n!)\ge18>1=v_2(1998)$, $v_3(n!)\ge 12>3=v_3(1998)$ and $v_{37}\ge 1=v_{37}(1998)$). All pairs of $(x,y)$ with $\gcd(x,y)=1998$ and $\operatorname{lcm}(x,y)=n!$ can be generated as follows by determining $v_p(x)$ and $v_p(y)$ for all primes $p\le n$:

• If $v_p(1998)=v_p(n!)$ (which holds only for $p>n$ or - if $37\le n<2\cdot 37$ - for $p=37$), we must let $v_p(x)=v_p(y)=b_p(1998)$.
• If $v_p(1998)<v_p(n!)$, we have a choice: Either let $v_p(x)=v_p(1998)$ and $v_p(y)=v_p(n!)$, or vice versa.

As each $p$ with $v_p(1998)<v_p(n!)$ gives us a binary choice, the number of our pairs $(x,y)$ is precisely $2^m$ where $m$ is the number of such primes. The problem statements calls for ordered pairs, hence we should rather use $2^{m-1}$ as count (as $v_2(1998)\ne v_2(n!)$, we cannot have pairs with $x=y$). As $2^{10}<1998<2^{11}$, the question is: For which $n$ is $m\le 11$?

If $37\le n<2\cdot 37$, then $m$ counts all primes $\le n$ except $p=37$ (because $v_{37}(n!)=1=v_p(1998)$). Hence this gives us a solution if and only if $n$ is less than the thirteenth prime, $41$.

If $37\le n<41$, then $n$ is a solution.

For all larger $n$, $m$ is too big. Hence

$n$ is a solution if and only if $n\le 40$.