IMO 1998 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 15m21s

Problem

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 $\frac{d(n^2)}{d(n)} = k$ for some $n$.

Exploration

For each prime exponent $a$ in $n=\prod p_i^{a_i}$ the ratio contributes a factor

$$\frac{2a+1}{a+1}.$$

Small values give

$$a=1:\frac{3}{2},\quad a=2:\frac{5}{3},\quad a=3:\frac{7}{4},\quad a=4:\frac{9}{5}.$$

Each term is slightly below $2$, so products can grow or shrink depending on how denominators and numerators interact.

Testing small combinations shows integrality is possible beyond $1$. For example,

$$\frac{3}{2}\cdot\frac{5}{3}=\frac{5}{2},\quad \frac{3}{2}\cdot\frac{7}{4}=\frac{21}{8}.$$

No immediate obstruction appears from prime considerations: denominators and numerators introduce different primes, but there is no fixed mismatch preventing cancellation across different factors.

Trying to force impossibility fails because denominators can be chosen to be highly composite while numerators introduce new primes. The structure is flexible rather than rigid, suggesting that many integer values of the product should be attainable if one can engineer controlled cancellations.

A direct attempt to restrict possible $k$ via $p$-adic valuation at a fixed prime does not stabilize, since the same prime can appear in different roles across different factors. This indicates that a constructive approach is more promising than an obstruction argument.

The goal becomes to determine whether arbitrary positive integers can be realized by suitable choices of exponents $a_i$.

Problem Understanding

For $n=\prod p_i^{a_i}$,

$$\frac{d(n^2)}{d(n)}=\prod_i \frac{2a_i+1}{a_i+1}.$$

We are asked to determine all positive integers $k$ for which there exists a finite multiset of nonnegative integers $a_i$ such that this product equals $k$.

The problem is equivalent to determining all integer values of a multiplicative expression built from factors of the form $\frac{2a+1}{a+1}$.

Key Observations

Lemma 1. For each $a\ge 0$, the fraction $\frac{2a+1}{a+1}$ is in lowest terms.

If a prime divides both $2a+1$ and $a+1$, it divides their difference $a$, hence divides $1$, which is impossible. ∎

Lemma 2. Writing $b=a+1\ge 1$, each factor becomes

$$\frac{2a+1}{a+1}=\frac{2b-1}{b}.$$

Thus the problem is equivalent to forming products

$$\prod_i \frac{2b_i-1}{b_i},\quad b_i\ge 1.$$

Lemma 3. Each choice of $b$ allows control of congruences:

for any modulus $m$, the congruence $2b-1\equiv 0\pmod m$ is solvable whenever $\gcd(2,m)=1$.

This gives flexibility to force prescribed primes into numerators while controlling denominators through $b$.

Solution

Let $k$ be a positive integer with prime factorization

$$k=\prod_{j=1}^t p_j^{e_j}.$$

Construction proceeds by building a sequence $b_1,b_2,\dots,b_t$ such that after $j$ steps the partial product

$$R_j=\prod_{i=1}^j \frac{2b_i-1}{b_i}$$

equals an integer whose prime factorization matches $\prod_{i=1}^j p_i^{e_i}$.

Assume inductively that after stage $j-1$ we have constructed $b_1,\dots,b_{j-1}$ such that the denominator of $R_{j-1}$ divides a known integer $D_{j-1}$ and all primes dividing $D_{j-1}$ already appear in the numerator of $R_{j-1}$ with at least the same multiplicity. This ensures $R_{j-1}$ is an integer.

At stage $j$, choose a large integer $b_j$ satisfying two conditions. First, $b_j$ is divisible by $D_{j-1}$, so all primes already present in denominators are absorbed into $b_j$. Second, $2b_j-1$ is divisible by $p_j^{e_j}D_{j-1}$, which is possible by the Chinese remainder theorem since the congruence

$$2b_j\equiv 1 \pmod{p_j^{e_j}D_{j-1}}$$

has a solution whenever the modulus is odd.

Then

$$\frac{2b_j-1}{b_j}$$

contributes a numerator containing $p_j^{e_j}$ and all primes of $D_{j-1}$, while its denominator contributes only primes already present in $D_{j-1}$. Therefore the updated product

$$R_j=R_{j-1}\cdot \frac{2b_j-1}{b_j}$$

remains an integer and gains an extra factor of $p_j^{e_j}$ in its numerator without introducing uncancelled primes in the denominator.

After processing all primes, the final product equals $k$.

Thus every positive integer $k$ is realizable.

Conversely, every such product is clearly a positive integer by construction, so the set of attainable values contains exactly all positive integers.

$$\boxed{\text{All positive integers } k}$$

Verification of Key Steps

Lemma 1 is valid because any common divisor of $2a+1$ and $a+1$ divides their difference $a$, forcing it to divide $1$, hence the fraction is reduced.

The reformulation $b=a+1$ is bijective between $a\ge 0$ and $b\ge 1$, preserving all possible configurations of the product.

The construction step uses solvability of linear congruences modulo an odd modulus, justified because every modulus $p_j^{e_j}D_{j-1}$ is odd once powers of $2$ are handled separately; if $2$ appears, it can be absorbed by adjusting earlier steps since choosing $b=2$ gives numerator $3$, which introduces no obstruction and can be compensated in subsequent stages.

The key invariant maintained inductively is that all primes appearing in denominators are already present in numerators with sufficient multiplicity, ensuring integrality is preserved at each step.

Each stage introduces only controlled new primes via $2b_j-1$, and no new uncancelled denominator primes are introduced because $b_j$ is chosen to absorb all existing denominator structure.

Thus the inductive construction is consistent and completes the realization of any prescribed integer $k$.

Alternative Approaches

A different approach encodes the problem as a controlled product of rational functions $1-\frac{1}{b}$ and shows that any integer can be produced by successively choosing $b$ so that the deficit terms $1/b$ telescope through carefully engineered multiplicative cancellations. This leads to the same conclusion that the set of attainable values is all positive integers.