Number theoryDifficulty 6.0National OlympiadProve itUnited States
Problem:
For a positive integer n, denote by τ(n) the number of positive integer divisors of n, and denote by ϕ(n) the number of positive integers that are less than or equal to n and relatively prime to n. Call a positive integer n good if φ(n)+4τ(n)=n. For example, the number 44 is good because φ(44)+4τ(44)=44. Find the sum of all good positive integers n.
Solution
Solution:
We claim that 44,56,72 are the only good numbers. It is easy to check that these numbers work.
Now we prove none others work. First, remark that as n=1,2 fail so we have φ(n) is even, thus n is even. This gives us φ(n)≤n/2. Now remark that τ(n)<2n, so it follows we need n/2+8n>n⟹n≤256. This gives us a preliminary bound. Note that in addition we have 8τ(n)>n.
Now, it is easy to see that powers of 2 fail. Thus let n=2ap1b where p1 is an odd prime. From 8τ(n)>n we get 8(a+1)(b+1)>2ap1b≥2a3b from which we get that (a,b) is one of (1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(3,2),(4,1) Remark that p1≤∗∗2a8(a+1)(b+1). From this we can perform some casework: - If a=1,b=1 then p1−1+16=2p1 but then p=15, absurd. - If a=1,b=2 then we have p1≤5 which is obviously impossible. - If a=1,b=3 then p1≤4 which is impossible. - If a=2,b=1 then p1≤12 and it is easy to check that p1=11 and thus n=44 is the only solution. - If a=2,b=2 then p1≤4 which is impossible. - If a=3,b=1 then p1≤8 and only p1=7 or n=56 works. - If a=3,b=2 then p1≤3 and p1=3,n=72 works. - If a=4,b=1 then p1≤1 which is absurd.
Now suppose n is the product of 3 distinct primes, so n=2ap1bp2c so we have 8(a+1)(b+1)(c+1)>2a3b5c then we must have (a,b,c) equal to one of (1,1,1),(1,2,1),(2,1,1),(3,1,1) Again, we can do some casework: - If a=b=c=1 then 8τ(n)=64>2p1p2 but then p1=3,p2=5 or p1=3,p2=7 is forced neither of which work. - If a=1,b=2,c=1 then 8τ(n)=96>2p12p2 but then p1=3,p2=5 is forced which does not work. - If a=2,b=1,c=1 then 8τ(n)=96>4p1p2 forces p1=3,p2=5 or p1=3,p2=7 neither of which work. - If a=3,b=1,c=1 then 8τ(n)=108>8p1p2 which has no solutions for p1,p2.
Finally, take the case where n is the product of at least 4 distinct primes. But then n≥2⋅3⋅5⋅7=210 and as 2⋅3⋅5⋅11>256, it suffices to check only the case of 210. But 210 clearly fails, so it follows that 44,56,72 are the only good numbers so we are done.
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.