Maths Olympiad Prep

Library / /126 of 220

Number theory Difficulty 6.1 National Olympiad Prove it Ukraine

Find the largest positive integer nn such that it has exactly 4 positive integer divisors (including 11 and nn), the sum SS of which satisfies the condition 40S4240 \le S \le 42.

Solution

In the case n=pqn = pq, S=1+p+q+pq=(1+p)(1+q)S = 1 + p + q + pq = (1+p)(1+q). Suppose p<qp < q.
Let us consider possible cases.
If S=40S = 40, then (p+1)(q+1)=40(p+1)(q+1) = 40. Since p+13p+1 \ge 3, the following cases are possible:
p+1=4,q+1=10p=3,q=9q is not prime. p+1=4, q+1=10 \Rightarrow p=3, q=9 \Rightarrow q \text{ is not prime.}
p+1=5,q+1=8p=4,q=7p is not prime. p+1=5, q+1=8 \Rightarrow p=4, q=7 \Rightarrow p \text{ is not prime.}
If S=41S = 41, then (p+1)(q+1)=41(p+1)(q+1) = 41, since 4141 is prime, there are no solutions.
If S=42S = 42, then (p+1)(q+1)=42(p+1)(q+1) = 42. The options are:
p+1=3,q+1=14p=2,q=13n=26. p+1=3, q+1=14 \Rightarrow p=2, q=13 \Rightarrow n=26.
p+1=6,q+1=7p=5,q=6q is not prime. p+1=6, q+1=7 \Rightarrow p=5, q=6 \Rightarrow q \text{ is not prime.}
So, in this case, we have a single number n=26n=26, which satisfies the conditions.
In case n=p3n = p^3, S=1+p+p2+p3S = 1 + p + p^2 + p^3. Note that if p=2p=2, then 1+p+p2+p3=151 + p + p^2 + p^3 = 15; if p=3p=3, 1+p+p2+p3=401 + p + p^2 + p^3 = 40; and if p4p \ge 4, 1+p+p2+p3851 + p + p^2 + p^3 \ge 85.
In this case, there is also a single number n=27n=27, which satisfies the conditions.

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.