Maths Olympiad Prep

Library / /1 of 9

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 mn2m \ge n \ge 2 satisfying
σ(m)1m1=σ(n)1n1=σ(mn)1mn1. \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)1pe1=(1+p++pe)1pe1=p(1++pe1)pe1=pp1. \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 AB=A+B1|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 and solution reproduced as published; topic and difficulty added by this site.