Maths Olympiad Prep

Library / /394 of 426

Number theory Difficulty 7.0 National Olympiad, round 2 Prove it Saudi Arabia

Find all positive integers nn, such that nn is a perfect number and φ(n)\varphi(n) is power of 2. Note: a positive integer nn is called perfect if the sum of all its positive divisors is equal to 2n2n.

Solution

Suppose that φ(n)=2m\varphi(n) = 2^m for some mZ+m \in \mathbb{Z}^+. Based on the formula of φ(n)\varphi(n), we have
φ(n)=pnpt1(p1)=2m \varphi(n) = \prod_{p|n} p^{t-1}(p-1) = 2^m
with vp(n)=tv_p(n) = t. This implies that t=1t = 1 for all odd prime divisors, since otherwise, p2mp \mid 2^m, a contradiction. Thus p1p-1 is a power of 2.

With odd prime divisor of nn, put p=2s+1p = 2^s + 1 for some sZ+s \in \mathbb{Z}^+. If s=1s = 1 then p=3p = 3, otherwise ss must be even since p(1)s+10(mod3)p \equiv (-1)^s + 1 \equiv 0 \pmod{3} when ss is odd, contradiction. In case ss has some proper odd prime divisor qq then put s=qts = qt with t>1t > 1 then 2s+1=(2t)q+12^s + 1 = (2^t)^q + 1 is divisible by 2t+12^t + 1, contradiction also.

These imply that ss is also a power of 2, so by putting s=2ks = 2^k, we get p=22k+1p = 2^{2k} + 1. Now let n=2ap1p2pln = 2^a p_1 p_2 \dots p_l with a0,l0a \ge 0, l \ge 0 and p1,p2,,plp_1, p_2, \dots, p_l are odd primes in ascending order, in which p1=22k+1p_1 = 2^{2k} + 1. So
2n=σ(n)=(2a+11)(p1+1)(p2+1)(pl+1) 2n = \sigma(n) = (2^{a+1} - 1)(p_1 + 1)(p_2 + 1)\dots(p_l + 1)
is the sum of divisors of nn. Note that l>0l > 0, otherwise, σ(n)=2a+11\sigma(n) = 2^{a+1}-1, contradiction. If p1>3p_1 > 3 then 32n3 \nmid 2n and
p1+1=22k+2=2(22k1+1)2((1)2k1+1)0(mod3) p_1 + 1 = 2^{2k} + 2 = 2(2^{2k-1} + 1) \equiv 2((-1)^{2k-1} + 1) \equiv 0 \pmod{3}
implying that 32n3 \mid 2n, contradiction. Thus p1=3p_1 = 3 and v3(2n)=1v_3(2n) = 1 leads to l2l \le 2. There are two cases

* If l=2l = 2 then 2a+13p2=(2a+11)4(p2+1)2^{a+1} \cdot 3 \cdot p_2 = (2^{a+1} - 1) \cdot 4 \cdot (p_2 + 1), note that v2(p2+1)=1v_2(p_2+1) = 1 so comparing the exponent of 2 in both sides to get a=2a = 2. Thus 6p2=7(p2+1)6p_2 = 7(p_2+1), contradiction.
* If l=1l = 1 then 2a+13=(2a+11)42^{a+1} \cdot 3 = (2^{a+1} - 1) \cdot 4, then a=1a = 1 implies that n=6n = 6 is a perfect square.

Therefore, n=6n = 6 is only solution of this problem.

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.