Maths Olympiad Prep

Library / /4 of 14

Number theory Difficulty 5.6 AIME, harder Prove it Bulgaria

For any positive integer m>1m > 1 denote by f(m)f(m) the sum of all positive integers which are less than mm and co-prime to mm. Find all positive integers nn such that there exist positive integers kk and ll such that f(nk)=nlf(n^k) = n^l.

Solution

If m>2m > 2 then the positive integers which are less than mm and co-prime to mm can be partitioned into pairs (k,mk)(k, m-k), mkkm-k \neq k. The number of these pairs is φ(m)2\frac{\varphi(m)}{2} and the sum of the numbers in every pair is mm. Therefore f(m)=mφ(m)2f(m) = \frac{m\varphi(m)}{2}, which is true for m=2m = 2 as well. Since φ(nk)=nk1φ(n)\varphi(n^k) = n^{k-1}\varphi(n), we obtain
f(nk)=nkφ(nk)2=n2k1φ(n)2. f(n^k) = \frac{n^k \varphi(n^k)}{2} = \frac{n^{2k-1} \varphi(n)}{2}.
Hence the given condition becomes n2k1φ(n)=2nln^{2k-1}\varphi(n) = 2n^l.
If l>2k1l > 2k-1, then we obtain φ(n)=2nl2k+12n\varphi(n) = 2n^{l-2k+1} \ge 2n, which is impossible. If l=2k1l = 2k-1 we get φ(n)=2\varphi(n) = 2, which gives n=3,4n = 3, 4 or 66. If l<2k1l < 2k-1, then n2k1lφ(n)=2n^{2k-1-l}\varphi(n) = 2, which is satisfied only by n=2n = 2 and 2k1l=12k-1-l = 1, i.e. l=2k2l = 2k-2.
Finally, the solutions are n=2,3,4n = 2, 3, 4 and 66.

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.