Maths Olympiad Prep

Library / /9 of 19

Number theory Difficulty 4.8 AIME Find the answer United States

For nn a positive integer, let f(n)f(n) be the quotient obtained when the sum of all positive divisors of nn is divided by nn. For example, f(14)=(1+2+7+14)÷14=127f(14) = (1 + 2 + 7 + 14) \div 14 = \frac{12}{7}. What is f(768)f(384)f(768) - f(384) ?

Pick one

Solution

Suppose all the positive divisors of nn are d1<d2<<dkd_1 < d_2 < \dots < d_k. Then
f(n)=d1+d2++dkn=d1n+d2n++dkn=1dk+1dk1++1d1. f(n) = \frac{d_1 + d_2 + \dots + d_k}{n} = \frac{d_1}{n} + \frac{d_2}{n} + \dots + \frac{d_k}{n} = \frac{1}{d_k} + \frac{1}{d_{k-1}} + \dots + \frac{1}{d_1}.
Thus f(n)f(n) is the sum of the reciprocals of the positive divisors of nn. Because 768=3842768 = 384 \cdot 2, all the divisors of 384384 also divide 768768, so it is necessary to consider only the divisors of 768768 that do not divide 384384, which are 282^8 and 2832^8 \cdot 3. Therefore
f(768)f(384)=128+1283=4283=1192. f(768) - f(384) = \frac{1}{2^8} + \frac{1}{2^8 \cdot 3} = \frac{4}{2^8 \cdot 3} = \frac{1}{192}.

Let σ(n)\sigma(n) be the sum of the divisors of nn. Then f(n)=σ(n)nf(n) = \frac{\sigma(n)}{n}, and because σ\sigma is multiplicative (meaning that σ(ab)=σ(a)σ(b)\sigma(ab) = \sigma(a)\sigma(b) whenever gcd(a,b)=1\gcd(a, b) = 1), ff is multiplicative as well. That is,
f(768)f(384)=f(283)f(273)=f(3)(f(28)f(27)). f(768) - f(384) = f(2^8 \cdot 3) - f(2^7 \cdot 3) = f(3)(f(2^8) - f(2^7)).
Note that f(3)=43f(3) = \frac{4}{3} and
f(2k)=σ(2k)2k=2k+112k=212k. f(2^k) = \frac{\sigma(2^k)}{2^k} = \frac{2^{k+1} - 1}{2^k} = 2 - \frac{1}{2^k}.
Thus
f(3)(f(28)f(27))=43128=1263=1192. f(3)(f(2^8) - f(2^7)) = \frac{4}{3} \cdot \frac{1}{2^8} = \frac{1}{2^6 \cdot 3} = \frac{1}{192}.

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.