Maths Olympiad Prep

Library / /13 of 19

Number theory Difficulty 8.3 Shortlist Prove it Estonia

Find all prime numbers pp for which one can find a positive integer mm and non-negative integers a0,a1,,ama_0, a_1, \dots, a_m less than pp such that
{a0+a1p++am1pm1+ampm=2013,a0+a1++am1+am=11. \begin{cases} a_0 + a_1 p + \dots + a_{m-1} p^{m-1} + a_m p^m = 2013, \\ a_0 + a_1 + \dots + a_{m-1} + a_m = 11. \end{cases}

Solution

Answer: 2003.

Subtracting the second equation from the first one gives
a1(p1)++am(pm1)=2002. a_1(p-1) + \dots + a_m(p^m - 1) = 2002.
As the l.h.s. of the obtained equality is divisible by p1p-1, 2002=2711132002 = 2 \cdot 7 \cdot 11 \cdot 13 must also be divisible by p1p-1. Thus p1p-1 equals one of 1,2,7,11,13,14,22,26,77,91,143,154,182,286,10011, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001 and 20022002. Since pp is prime, only 2,3,232, 3, 23 and 20032003 remain. The first equation of the given system is the pp-ary representation of 2013, whence the coefficients aia_i are uniquely determined by pp.

Now we study all cases.
1. If p=2p=2 then m=10m=10 as 210<2013<2112^{10} < 2013 < 2^{11}. The second equation implies that all aia_is must be ones, but 1+2+22++210=2111=20471+2+2^2+\dots+2^{10} = 2^{11}-1 = 2047. Hence there is no solution in this case.

2. Let p=3p=3. As 2013=23+32+233+235+2362013 = 2 \cdot 3 + 3^2 + 2 \cdot 3^3 + 2 \cdot 3^5 + 2 \cdot 3^6 whereas 2+1+2+2+2=9112+1+2+2+2 = 9 \neq 11, this case gives no solution either.

3. Let p=23p=23. As 2013=12+1823+32322013 = 12 + 18 \cdot 23 + 3 \cdot 23^2 while 12+18+3>1112 + 18 + 3 > 11, this case gives no solution either.

4. For p=2003p=2003, we get 2013=10+20032013 = 10+2003 and 10+1=1110+1=11, so the conditions are satisfied.
Consequently, 2003 is the only prime number with the desired property.

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.