Maths Olympiad Prep

Library / /117 of 462

Number theory Difficulty 5.3 AIME, harder Prove it Ireland

Find, with proof, the greatest positive integer which cannot be expressed in the form 17x+127y17x + 127y, with xx and yy non-negative integers.

Solution

The answer is 20152015. To prove this, first, observe (using Euclid's algorithm, for example), that
15172127=1(1) 15 \cdot 17 - 2 \cdot 127 = 1 \qquad (1)
Next, note that
2016=(171)(1271)=1612717+1=1612717+15172127=14127+1417 \begin{align*} 2016 &= (17 - 1)(127 - 1) = 16 \cdot 127 - 17 + 1 \\ &= 16 \cdot 127 - 17 + 15 \cdot 17 - 2 \cdot 127 \tag{2} \\ &= 14 \cdot 127 + 14 \cdot 17 \end{align*}
We now claim: If z>2016z > 2016 is an integer, then z=127a+17bz = 127a + 17b, for some non-negative integers a,ba, b.
To prove the claim, we note that by (1), z=127c+17dz = 127c + 17d, for some integers c,dc, d, and then z=127(c+17y)+17(d127y)z = 127(c + 17y) + 17(d - 127y), for any integer yy. So we can write
z=127a+17b, with integers a,b with a0. z = 127a + 17b, \text{ with integers } a, b \text{ with } a \ge 0.
Choose such a representation with bb greatest possible. If b0b \ge 0, the Claim is established. Suppose, for the sake of contradiction, that b<0b < 0. Then z=127(a17)+17(b+127)z = 127(a - 17) + 17(b + 127), and, thus, by our choice of bb, a17<0a - 17 < 0, and thus z=127a+17b1271617<2016z = 127a + 17b \le 127 \cdot 16 - 17 < 2016, contradicting our hypotheses. So the Claim is proved.
Combining this with (2), we see that every integer w2016w \ge 2016 is expressible as w=17x+127yw = 17x + 127y, for some non-negative integers x,yx, y.
Finally, suppose that 2015=1612717=17u+127v2015 = 16 \cdot 127 - 17 = 17u + 127v, for some non-negative integers u,vu, v. Then, using subtraction, 127(16v)=17(u+1)127(16 - v) = 17(u + 1). This shows that the positive number u+1u + 1 is divisible by 127127 and so u126u \ge 126, implying that 2015171262015 \ge 17 \cdot 126, which is false. Hence 20152015 is the integer sought.

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.