Maths Olympiad Prep

Library / /21 of 39

Number theory Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

Alessandra writes in (Luigi's) notebook all natural numbers nn that have both of the following properties: nn has exactly 4 positive divisors (including 1 and nn itself), and the sum of the positive divisors of nn equals 42. What is the sum of all the numbers written by Alessandra?

Pick one

Solution

Solution:

The answer is (D). If nn has four positive divisors, they are, in increasing order, 1,p,q,n1, p, q, n with pp a prime number.
If qq is a prime number, we can conclude that n=pqn = p \cdot q, because nn has no other divisors. The sum of the positive divisors is 1+p+q+pq=(1+p)+q(1+p)=(1+p)(1+q)1 + p + q + p \cdot q = (1 + p) + q(1 + p) = (1 + p)(1 + q) which by hypothesis must equal 42=23742 = 2 \cdot 3 \cdot 7. Neither (1+p)(1 + p) nor (1+q)(1 + q) can equal 1, nor can either equal 42, otherwise the other would equal 1. Since 42 has only three prime factors, one of them equals (1+p)(1 + p) or (1+q)(1 + q), and hence must still be prime when decreased by one. The only possibility is therefore that p+1=3p + 1 = 3 and q+1=27=14q + 1 = 2 \cdot 7 = 14. Since p=31=2p = 3 - 1 = 2 and q=141=13q = 14 - 1 = 13 are prime, n=213=26n = 2 \cdot 13 = 26 has the required properties.

Let us now consider the other possibility, that qq is not a prime number. Then qq has as divisors only 1,p1, p and itself, otherwise other divisors would also divide nn. Thus q=p2q = p^{2} and n=p3n = p^{3}. The sum of the positive divisors is 1+p+p2+p3=1+p(1+p+p2)=421 + p + p^{2} + p^{3} = 1 + p(1 + p + p^{2}) = 42, so p(1+p+p2)=41p(1 + p + p^{2}) = 41. But, since 41 is a prime number, in this case there are no solutions.

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 it; metadata (topic, difficulty) added by this project.