Maths Olympiad Prep

Library / /44 of 52

Number theory Difficulty 8.6 Shortlist Prove it Romania

For every positive integer nn, let σ(n)\sigma(n) denote the sum of all positive divisors of nn (1 and nn, inclusive). Show that a positive integer nn, which has at most two distinct prime factors, satisfies the condition σ(n)=2n2\sigma(n) = 2n - 2 if and only if n=2k(2k+1+1)n = 2^k(2^{k+1} + 1), where kk is a non-negative integer and 2k+1+12^{k+1} + 1 is prime.

Solution

1+1pσ(pl)pl=p1plp1<pp1, 1 + \frac{1}{p} \le \frac{\sigma(p^l)}{p^l} = \frac{p - \frac{1}{p^l}}{p-1} < \frac{p}{p-1},

(2k+11)(1+1p)σ(n)pl=2k+12pl<(2k+11)pp1. (2^{k+1} - 1) \left(1 + \frac{1}{p}\right) \le \frac{\sigma(n)}{p^l} = 2^{k+1} - \frac{2}{p^l} < (2^{k+1} - 1) \frac{p}{p-1}.
By the first inequality, (2k+11)(1+1/p)<2k+1(2^{k+1}-1)(1+1/p) < 2^{k+1}, so p>2k+11p > 2^{k+1}-1, i.e., p2k+1+1p \ge 2^{k+1}+1 since pp is odd. On the other hand, p<2k+1+2(p1)/plp < 2^{k+1}+2(p-1)/p^l, by the second inequality, so 2(p1)>pl2(p-1) > p^l, and consequently l=1l=1 and p=2k+1+1p = 2^{k+1}+1.
To rule out the case n=pkqln = p^k q^l, where pp and qq are distinct odd primes, and kk and ll are positive integers, write
22n=σ(n)n=σ(pk)pkσ(ql)ql<pp1qq1. 2 - \frac{2}{n} = \frac{\sigma(n)}{n} = \frac{\sigma(p^k)}{p^k} \cdot \frac{\sigma(q^l)}{q^l} < \frac{p}{p-1} \cdot \frac{q}{q-1}.
Alternatively, but equivalently,
1p1+1q1+1(p1)(q1)+2n>1, \frac{1}{p-1} + \frac{1}{q-1} + \frac{1}{(p-1)(q-1)} + \frac{2}{n} > 1,
so min(p,q)=3\min(p, q) = 3, say p=3p=3. Then 3/(q1)+4/n>13/(q-1)+4/n > 1, and it follows that q=5q=5 and k=l=1k=l=1, i.e., n=15n=15 which does not satisfy the condition σ(n)=2n2\sigma(n) = 2n-2. This completes the proof.

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.