Maths Olympiad Prep

Library / /18 of 40

Number theory Difficulty 5.9 AIME, harder Prove it China

For positive composite number nn, denote by f(n)f(n) and g(n)g(n) the sum of the smallest three positive divisors of nn and the largest two positive divisors of nn, respectively. Find all nn such that g(n)g(n) equals f(n)f(n) to some power of positive integers. (posed by He Yijie)

Solution

If nn is odd, then all factors of nn are odd. So f(n)f(n) is odd and g(n)g(n) is even. g(n)g(n) cannot be f(n)f(n) to some power of positive integer. Therefore nn is even. The smallest two divisors of nn are 11 and 22, and the largest two divisors of nn are nn and n/2n/2.

Let dd be the third smallest divisor of nn. If there exists kNk \in \mathbb{N}^* such that g(n)=fk(n)g(n) = f^k(n), then

3n2=(1+2+d)k=(3+d)kdk(mod3). \frac{3n}{2} = (1 + 2 + d)^k = (3 + d)^k \equiv d^k \pmod{3}.

Since 33n23 \nmid \frac{3n}{2}, we see that 3dk3 \mid d^k. So 3d3 \mid d, and since dd is the third smallest, we see that d=3d = 3.

Thus, 32n=6k\frac{3}{2}n = 6^k, we get n=4×6k1n = 4 \times 6^{k-1}. Since 3n3 \nmid n, we see that k2k \ge 2.

Summing up, n=4×6l (lN)n = 4 \times 6^l \ (l \in \mathbb{N}^*).

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.