Maths Olympiad Prep

Library / Irish Mathematical Olympiad /64 of 236

Irish Mathematical Olympiad

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
15⋅17−2⋅127=1(1) 15 \cdot 17 - 2 \cdot 127 = 1 \qquad (1)
Next, note that
2016=(17−1)(127−1)=16⋅127−17+1=16⋅127−17+15⋅17−2⋅127=14⋅127+14⋅17 \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(d−127y)z = 127(c + 17y) + 17(d - 127y), for any integer yy. So we can write
z=127a+17b, with integers a,b with a≥0. z = 127a + 17b, \text{ with integers } a, b \text{ with } a \ge 0.
Choose such a representation with bb greatest possible. If b≥0b \ge 0, the Claim is established. Suppose, for the sake of contradiction, that b<0b < 0. Then z=127(a−17)+17(b+127)z = 127(a - 17) + 17(b + 127), and, thus, by our choice of bb, a−17<0a - 17 < 0, and thus z=127a+17b≤127⋅16−17<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 w≥2016w \ge 2016 is expressible as w=17x+127yw = 17x + 127y, for some non-negative integers x,yx, y.
Finally, suppose that 2015=16⋅127−17=17u+127v2015 = 16 \cdot 127 - 17 = 17u + 127v, for some non-negative integers u,vu, v. Then, using subtraction, 127(16−v)=17(u+1)127(16 - v) = 17(u + 1). This shows that the positive number u+1u + 1 is divisible by 127127 and so u≥126u \ge 126, implying that 2015≥17⋅1262015 \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,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.