Maths Olympiad Prep

Library / /39 of 397

Number theory Difficulty 4.9 AIME Prove it Taiwan

Define fk(n)f_k(n) to be the sum of the kk-th powers of all positive divisors of the positive integer nn, that is,
fk(n):=mn,m>0mk. f_k(n) := \sum_{m|n, m>0} m^k.
Find all pairs of positive integers (a,b)(a, b) such that fa(n)fb(n)f_a(n) \mid f_b(n) holds for all positive integers nn.

Solution

a=ba = b is the only possibility.

First, substituting n=2n = 2, we must have 1+2a1+2b1 + 2^a \mid 1 + 2^b. Let b=aq+rb = aq + r, where 0r<a0 \le r < a, then we know
1+2b=1+2aq+r1+(1)q×2r(mod1+2a). 1 + 2^b = 1 + 2^{aq + r} \equiv 1 + (-1)^q \times 2^r \pmod{1 + 2^a}.
Since 1+(1)q×2r<1+2a|1 + (-1)^q \times 2^r| < 1 + 2^a, we must have 1+(1)q×2r=01 + (-1)^q \times 2^r = 0, so qq is odd and r=0r = 0. In other words, bb must be an odd multiple of aa.

We now prove that q=1q = 1. Suppose for contradiction that qq has an odd prime factor pp, and let q=lpq = lp, so b=lpab = lpa. Take n=2p1n = 2^{p-1}, then we must have
2pa12a1=1+2a++2(p1)a=fa(n)fb(n)=1+2b++2(p1)b.(1) \frac{2^{pa} - 1}{2^a - 1} = 1 + 2^a + \cdots + 2^{(p-1)a} = f_a(n) \mid f_b(n) = 1 + 2^b + \cdots + 2^{(p-1)b}. \quad (1)
However,
1+2b++2(p1)b1+1++1=p(mod2pa1), 1 + 2^b + \cdots + 2^{(p-1)b} \equiv 1 + 1 + \cdots + 1 = p \pmod{2^{pa} - 1},
and 0<p<1+2a++2(p1)a0 < p < 1 + 2^a + \cdots + 2^{(p-1)a}, so the divisibility in (1) is impossible, a contradiction.

Therefore qq cannot have an odd prime factor, that is, q=1q = 1. 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 translated into English from zh; metadata (topic, difficulty) added by this project.