Maths Olympiad Prep

Library / /60 of 155

Number theory Difficulty 5.8 AIME, harder Prove it Saudi Arabia

Call a positive integer N2N \geq 2 "special" if for every kk such that 2kN2 \leq k \leq N, NN can be expressed as a sum of kk positive integers that are relatively prime to NN (although not necessarily relatively prime to each other). Find all special positive integers.

Solution

We claim that all odd numbers are special, and the only special even number is 22. For any even N>2N > 2, the number relatively to NN must be odd, and NN cannot be expressed as a sum of 33 positive odd numbers.

Now, suppose that NN is odd. We consider the binary decomposition of NN
N=2a1+2a2++2ai. N = 2^{a_{1}} + 2^{a_{2}} + \ldots + 2^{a_{i}}.
Note that (2t,N)=1(2^{t}, N) = 1 and i<log2N+1i < \log_{2} N + 1.

For any ik<N1i \leq k < N-1, suppose that NN can be expressed as a sum of kk powers of 22, i.e. N=2x1++2xkN = 2^{x_{1}} + \ldots + 2^{x_{k}}. Then at least one of xj>0x_{j} > 0 (otherwise, k=Nk = N). Suppose that x1>0x_{1} > 0 then
N=2x11+2x11+2x2++2xk. N = 2^{x_{1}-1} + 2^{x_{1}-1} + 2^{x_{2}} + \ldots + 2^{x_{k}}.
So NN can be expressed as a sum of k+1k+1 powers of 22. This implies that, for any k<log2N+1k < \log_{2} N + 1, NN can be expressed as a sum of kk positive integers that are relatively prime to NN.

Now, start from k=2k = 2. Let 2a2^{a} be the largest power of 22 such that 2a<N2^{a} < N. Then N=2a+(N2a)N = 2^{a} + (N - 2^{a}). Using the above argument, we can write 2a2^{a} as the sum of kk powers of 22 for any 1<k<2a1 < k < 2^{a}. Since 2a>N/22^{a} > N / 2, we have NN can be expressed as a sum of kk positive integers that are relatively prime to NN for any 2kN/22 \leq k \leq N / 2.

Since N/2+1>log2NN / 2 + 1 > \log_{2} N for all N3N \geq 3, we conclude that all N>3N > 3 odd are special.

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.