Competition problem — Number theory

Library / /20 of 36

Number theory Difficulty 5.9 AIME, harder Prove it Saudi Arabia

On the board is written a (not necessarily positive) integer. In a move, if the current number on the board is $a$ , one erases it and replaces it by either $a^2 + 2a + 3$ or $5a^2 + 2$ or $a - 119$ . Is there a starting number $s$ such that for any positive integer $f$ one can reach $f$ from $s$ with finitely many moves?

Solution

Note that all of numbers of form $119k$ and $119k-1$ cannot be represented as $a^2 + 2a + 3$ or $5a^2 + 2$ . We can check this claim by consider modulo 7 and 17. Indeed,
* If $119k = a^2 + 2a + 3 = (a+1)^2 + 2$ then $-2$ is quadratic residue modulo 7, clearly absurd since quadratic residue modulo 7 are 0, 1, 2, 4.
* If $119k = 5a^2 + 2$ then 3 is a quadratic residue modulo 17, also absurd.
* If $119k - 1 = a^2 + 2a + 3$ then $-3$ is quadratic residue modulo 17, also absurd.
* If $119k - 1 = 5a^2 + 2$ then $-2$ is quadratic residue modulo 7, also absurd.
So if we consider the first number in one of the above forms in which we run into when going backwards, it turns out that we can only shift by multiples of 117 and hence cannot obtain any number of the other form. ☐

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.