Maths Olympiad Prep

Library / /4 of 29

Number theory Difficulty 5.8 AIME, harder Prove it United States

For every positive integer NN, let σ(N)\sigma(N) denote the sum of the positive integer divisors of NN. Find all integers m≥n≥2m \ge n \ge 2 satisfying
σ(m)−1m−1=σ(n)−1n−1=σ(mn)−1mn−1. \frac{\sigma(m) - 1}{m - 1} = \frac{\sigma(n) - 1}{n - 1} = \frac{\sigma(mn) - 1}{mn - 1}.

Solution

The answer is that mm and nn should be powers of the same prime number. These all work because for a prime power we have
σ(pe)−1pe−1=(1+p+⋯+pe)−1pe−1=p(1+⋯+pe−1)pe−1=pp−1. \frac{\sigma(p^e) - 1}{p^e - 1} = \frac{(1 + p + \cdots + p^e) - 1}{p^e - 1} = \frac{p(1 + \cdots + p^{e-1})}{p^e - 1} = \frac{p}{p-1}.
So we now prove these are the only ones. Let λ\lambda be the common value of the three fractions.

Claim — Any solution (m,n)(m, n) should satisfy d(mn)=d(m)+d(n)−1d(mn) = d(m) + d(n) - 1.

Proof. The divisors of mnmn include the divisors of mm, plus mm times the divisors of nn (counting mm only once). Let λ\lambda be the common value; then this gives
σ(mn)≥σ(m)+mσ(n)−m=(λm−λ+1)+m(λn−λ+1)−m=λmn−λ+1 \begin{aligned} \sigma(mn) &\ge \sigma(m) + m\sigma(n) - m \\ &= (\lambda m - \lambda + 1) + m(\lambda n - \lambda + 1) - m \\ &= \lambda mn - \lambda + 1 \end{aligned}
and so equality holds. Thus these are all the divisors of mnmn, for a count of d(m)+d(n)−1d(m) + d(n) - 1. □\square

Claim — If d(mn)=d(m)+d(n)−1d(mn) = d(m) + d(n) - 1 and min⁡(m,n)≥2\min(m, n) \ge 2, then mm and nn are powers of the same prime.

Proof. Let AA denote the set of divisors of mm and BB denote the set of divisors of nn. Then ∣A⋅B∣=∣A∣+∣B∣−1|A \cdot B| = |A| + |B| - 1 and min⁡(∣A∣,∣B∣)>1\min(|A|, |B|) > 1, so ∣A∣|A| and ∣B∣|B| are geometric progressions with the same ratio. It follows that mm and nn are powers of the same prime. □\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.