4
$\begingroup$

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

$\endgroup$
16
  • 1
    $\begingroup$ Where did $m$ come from? $\endgroup$ Commented Sep 23, 2021 at 3:14
  • 2
    $\begingroup$ 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$? $\endgroup$ Commented Sep 23, 2021 at 3:14
  • 3
    $\begingroup$ @user2661923 note that he wrote that exponents can be 0 $\endgroup$ Commented Sep 23, 2021 at 4:08
  • 1
    $\begingroup$ I remember this, this was one of the questions from the 2019 IMO selection exams in Germany, there is a solution here (in German). $\endgroup$
    – leoli1
    Commented Sep 23, 2021 at 12:48
  • 1
    $\begingroup$ @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 $\endgroup$ Commented Sep 23, 2021 at 16:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .