Maths Olympiad Prep

Library / IMO Team Selection Contest /13 of 21

IMO Team Selection Contest

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+⋯+am−1pm−1+ampm=2013,a0+a1+⋯+am−1+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(p−1)+⋯+am(pm−1)=2002. a_1(p-1) + \dots + a_m(p^m - 1) = 2002.
As the l.h.s. of the obtained equality is divisible by p−1p-1, 2002=2⋅7⋅11⋅132002 = 2 \cdot 7 \cdot 11 \cdot 13 must also be divisible by p−1p-1. Thus p−1p-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=211−1=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=2⋅3+32+2⋅33+2⋅35+2⋅362013 = 2 \cdot 3 + 3^2 + 2 \cdot 3^3 + 2 \cdot 3^5 + 2 \cdot 3^6 whereas 2+1+2+2+2=9≠112+1+2+2+2 = 9 \neq 11, this case gives no solution either.

3. Let p=23p=23. As 2013=12+18⋅23+3⋅2322013 = 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.