# There exists a positive integer $s$ for which the number of divisors of $sn$ and of $sk$ are equal.

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.$$

• Where did $m$ come from? Commented Sep 23, 2021 at 3:14
• It seems to me that if $\displaystyle n = \prod_{i=1}^r (p_i)^{\alpha_i}$ and $\displaystyle k = \prod_{i=1}^t (q_i)^{\beta_i}$ where $p_1,\cdots,p_r, q_1, \cdots q_t$ are prime numbers, and if $\displaystyle T_n = \prod_{i=1}^r (\alpha_i + 1) = T_k = \prod_{i=1}^t (\beta_i + 1)$ then $n,k$ are automatically a satisfactory pair. So, the question is, under what circumstances can $n,k$ be a satisfactory pair, even though $T_n \neq T_k$? Commented Sep 23, 2021 at 3:14
• @user2661923 note that he wrote that exponents can be 0 Commented Sep 23, 2021 at 4:08
• I remember this, this was one of the questions from the 2019 IMO selection exams in Germany, there is a solution here (in German). Commented Sep 23, 2021 at 12:48
• @user69608 Suppose that $\displaystyle n = \prod_{i=1}^r (p_i)^{\alpha_i}, k = \prod_{i=1}^t (q_i)^{\beta_i}$. Here, I intend that $S_1 = \{p_1, \cdots, p_r\}$ are all distinct primes, as are $S_2 = \{q_1, \cdots, q_t\}$, while $S_1$ and $S_2$ may or may not intersect. Choose any prime $a$ that is not in $S_1 \cup S_2$, and choose any positive integer exponent $b$, so that $s = a^b$. Then the number of factors of $s\times n$ will be the number of factors of $n \times (b+1)$. Ditto for the factors of $s \times k$. ...see next comment Commented Sep 23, 2021 at 16:03

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:

1. Set A: Those that appear more often in $$n$$ than in $$k$$.
2. Set B: Those that appear more often in $$k$$ than in $$n$$.
3. Set C: Those that appear equal often in $$k$$ and $$n$$. -> These do not matter. We can ignore them (EG Primes that occur in neither).

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.