Maths Olympiad Prep

Library / /87 of 108

Number theory Difficulty 6.8 National Olympiad Prove it Mongolia

Let us say that an integer number is a power number, if there exist positive integers aa and nn such that the number equals to ana^n and n>1n > 1.

a) Prove that there exist 20102010 positive integers such that every sum of the integers selected from them is not a power number.

b) Prove that there exist 20102010 positive integers such that every sum of the integers selected from them is a power number.

Solution

a) Let pip_i be the ii-th prime number. Consider the numbers
p1, p12p2, p12p22p3, , p12p22p2009p2010. p_1,\ p_1^2 p_2,\ p_1^2 p_2^2 p_3,\ \dots,\ p_1^2 p_2^2 \dots p_{2009} p_{2010}.
If p12p22pk2pk+1p_1^2 p_2^2 \dots p_k^2 p_{k+1} is the least number in the sum, then the sum is divisible by pk+1p_{k+1}, but not divisible by pk+12p_{k+1}^2. Hence each sum formed from the given numbers is not a power number.

b) Let us show that for any given integers a1,a2,,ana_1, a_2, \dots, a_n there exists bNb \in \mathbb{N} such that ba1,ba2,,banb a_1, b a_2, \dots, b a_n are all power numbers. Suppose that ai=p1αi1p2αi2pkαika_i = p_1^{\alpha_{i1}} p_2^{\alpha_{i2}} \dots p_k^{\alpha_{ik}}, i=1,ni = 1, n, 0αij0 \le \alpha_{ij} and b=p1α1p2α2pkαkb = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}. If baib a_i is a power number, then there exists qiq_i (qi>1q_i > 1) such that α1+αi1,α2+αi2,,αk+αik\alpha_1 + \alpha_{i_1}, \alpha_2 + \alpha_{i_2}, \dots, \alpha_k + \alpha_{i_k} are all divisible by qiq_i.

Let qiq_i be the ii-th prime number. By the Chinese Remainder Theorem there exists αs\alpha_s such that αsαis(modqs)\alpha_s \equiv -\alpha_{i_s} \pmod{q_s}, for i=1,ni = 1, n and s=1,ks = 1, k.

Now we choose arbitrary 20102010 positive integers: a1,a2,,a2010a_1, a_2, \dots, a_{2010}. Let S1,S2,,S20101S_1, S_2, \dots, S_{2010-1} be all the sums formed by them. Then there exists bb such that bS1,bS2,,bS20101b S_1, b S_2, \dots, b S_{2010-1} are all power numbers. Thus, ba1,ba2,,ba2010b a_1, b a_2, \dots, b a_{2010} are the desired numbers.

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.