IMO 1998 · Problem 3

For any positive integer \(n\), let \(d(n)\) denote the number of positive divisors of \(n\) (including \(1\) and \(n\) itself). Determine all positive integers \(k\) such that \(d(n^2)/d(n) = k\) for some \(n\).

Official text of the problem. Official problem paper (PDF)

Answer

All positive odd integers: \[ \boxed{k=1,3,5,7,\ldots}. \]

Solution

If \(n=\prod_{i=1}^{s}p_i^{e_i}\) is its prime factorization, then \[ d(n)=\prod_{i=1}^{s}(e_i+1), \qquad d(n^2)=\prod_{i=1}^{s}(2e_i+1). \] Indeed, a divisor is determined by choosing the exponent of each prime independently. These formulas also hold for \(n=1\), with empty products.

In particular, \(d(n^2)\) is odd. Thus, if \(d(n^2)=k\,d(n)\), then \(k\) must be odd.

We now prove that every positive odd integer occurs. For a positive odd integer \(t\), put \[ F(t)=\frac{2t-1}{t}, \] and let \(\mathcal S\) be the set of all finite products of such numbers, including the empty product \(1\). This set is closed under multiplication. Moreover, every element of \(\mathcal S\) is a possible divisor ratio: for distinct primes \(q_1,\ldots,q_m\), choosing \[ n=\prod_{i=1}^{m}q_i^{t_i-1} \] gives \[ \frac{d(n^2)}{d(n)} =\prod_{i=1}^{m}\frac{2t_i-1}{t_i}. \]

We need the following identity-based lemma.

Lemma. For every positive odd integer \(a\) and every integer \(r\geq1\), \[ \frac{2^r a-1}{a}\in\mathcal S. \]

Proof. We induct on \(r\), proving the assertion for all positive odd \(a\) simultaneously. For \(r=1\), the expression is \(F(a)\).

Suppose \(r\geq2\) and the assertion holds for \(r-1\). Set \[ b=2a+1,\qquad c=2^{r-1}b-1. \] Both \(b\) and \(c\) are positive odd integers. By the induction hypothesis, \[ \frac cb=\frac{2^{r-1}b-1}{b}\in\mathcal S. \] Also \(F(ac)\in\mathcal S\). Since \[ 2ac-1 =2a(2^{r-1}b-1)-1 =2^rab-b =b(2^ra-1), \] their product is \[ F(ac)\frac cb =\frac{2ac-1}{ac}\frac cb =\frac{2^ra-1}{a}. \] This proves the lemma. \(\square\)

Finally, we use strong induction on the positive odd integer \(k\) to prove \(k\in\mathcal S\). The case \(k=1\) is the empty product, realized by \(n=1\).

For \(k>1\), write \[ k+1=2^r a, \] where \(r\geq1\) and \(a\) is positive and odd. We have \[ a\leq\frac{k+1}{2}<k, \] so \(a\in\mathcal S\) by induction. The lemma gives \[ \frac{k}{a}=\frac{2^ra-1}{a}\in\mathcal S. \] Multiplying these two elements shows that \(k\in\mathcal S\), and hence \(k=d(n^2)/d(n)\) for some positive integer \(n\).

Therefore precisely the positive odd integers occur.

The solution was checked against Evan Chen's published IMO solution notes.