IMO 2018 SL N1: Determine all pairs $(n, k)$ of distinct positive integers such that there exists a positive integer $s$ for which the number of divisors of $sn$ and of $sk$ are equal.
I am stuck. Here is my progress.
If $k|n$ then it is not possible.
Let $k={p_1}^{\alpha_1}\cdot{p_2}^{\alpha_2}\dots \cdots {p_m}^{\alpha_m}. $
Let $n={p_1}^{\beta_1}\cdot{p_2}^{\beta_2}\dots \cdots {p_m}^{\beta_m}. $
Where $\alpha_i, \beta_i\ge 0.$
Then the number of divisors of $k$ is $ (\alpha_1+1)\dots(\alpha_m+1)$ and of $n$ is $(\beta_1+1)\dots(\beta_m+1).$
Now there will be a exponent $\alpha_i$ such that $\alpha_i>\beta_i.$ If not then $k|n.$ Say WLOG $\alpha_1>\beta_1.$
Similarly there will be a exponent $\alpha_i$ such that $\alpha_i<\beta_i.$ If not then $m|n.$ Say WLOG $\alpha_2<\beta_2.$
Now we can probably let $S=p_1^a\cdot p_2^b.$
We want $(\alpha_3+1)\dots(\alpha_m+1)(a+\alpha_1+1)(b+\alpha_2+1)=(\beta_3+1)\dots(\beta_m+1)(a+\beta_1+1)(b+\beta_2+1).$
We can treat $(\alpha_3+1)\dots(\alpha_m+1)=Y$ as a constant and $(\beta_3+1)\dots(\beta_m+1)=Z$ as constant.
I am not sure on how to proceed. We just have to construct those $a,b.$
Best Answer
You're on the right track, however:
Looking at your $ S = p_1 ^a \times p_2 ^b$ hypothesis, we want to solve the general equation:
$$(a + \alpha_1 + 1)(b+\alpha_2 + 1 ) Y = (a+\beta_1 + 1 ) ( b+ \beta_2 + 1 ) Z.$$
For $\alpha_1 > \beta_1$, we have $ 1 < \frac{ a +\alpha_1 + 1 } { a + \beta_1 + 1 } \leq \frac{ \alpha_1 + 1 }{\beta_1 + 1 }.$
For $ \alpha_2 < \beta_2$, we have $ \frac{\alpha_2 + 1 } { \beta_2 + 1 } \leq \frac{ b +\alpha_2 + 1 } { b + \beta_2 + 1 } < 1 $.
So, if a solution exists, we require $ \frac{\alpha_2 + 1 } { \beta_2 + 1 } < \frac{Z}{Y} < \frac{ \alpha_1 + 1 }{\beta_1 + 1 }$.
There are clearly counter examples to this constraint, thus the simplistic $ S = p_1 ^a \times p_2 ^b$ isn't sufficient.
In particular, this argument strongly suggests that we want to bound the "leftover term $\frac{Z}{Y}$" very closely to 1, which happens when all of the prime factors are involved.
If you haven't already done this, I strongly suggest showing that an $s$ exists for the small cases $ (n,k) = (2, 3), (4, 3), (12, 18), (6,5), (30, 7), (30, 77)$.
It is from working with these cases that I found the following solution.
There are 3 types of primes to consider:
As you realized, a necessary condition is $ n \not \mid k, k \not \mid n$.
This means that sets $A$, $B$ are non-empty, which is crucial.
As it turns out, the necessary condition is also a sufficient condition (to be shown).
Claim: There exists a $D$ such that for any $d \geq D$, we can find integers $\alpha_i$ such that
$$ \prod_{p_i \in A} \frac{ v_{p_i} (n) + \alpha_i + 1 } { v_{p_i} (k) + \alpha_i + 1 } = \frac{d+1}{d}. $$
Likewise, there exists a $E$ such that for any $ e \geq E$, we can find integers $\beta_j$ such that
$$ \prod_{q_j \in B} \frac{ v_{q_j} (k) + \beta_j + 1 } { v_{q_j} (n) + \beta_j + 1 } = \frac{e+1}{e}. $$
Corollary: Take $d= e = \max(D, E)$ and the corresponding integers.
Then for $s = \prod p_i ^ {\alpha_i} \times \prod q_j^{\beta_j}$, we get that $\sigma(sn) = \sigma(sk)$.
So the condition $ n\not\mid k, k\not\mid n$ is sufficient.
Proof of claim: Try this for yourself. If you're stuck, state what you've tried.
As a cryptic hint, set up a another claim in a similar manner to the claim.