P124.4.2.2019.3.2   $1019$ stones are placed into two non-empty boxes. Each second Alex chooses a box with an even amount of stones and shifts half of these stones into another box.
Prove that for each $k$, $1\le k\le1018$, at some moment there will be a box with exactly $k$ stones.

Solution

Note that $1019$ is prime and $\frac{1019-1}{2} = 509$ is prime as well.

Let $b_1, b_2$ be variables which correspond to the number of stones in the two boxes. Observe that $b_1 + b_2 = 1019$ at all times. Now, notice that every move halves each of $b_1, b_2$ modulo $1019.$ In other words, if $(b_1, b_2)$ are turned into $(b_1', b_2')$ after Alex does his shifting, then we have $1019 | b_1 - 2b_1', b_2 - 2b_2'.$ With this observation, it would suffice to prove that $2$ is either a primitive root modulo $1019$ or is the square of the primitive. This is equivalent to $ord_{1019}(2) \in \{509, 1019\}$, and so we just need to show that $ord_{1019}(2) \notin \{1, 2\}.$ However, this is obvious since $1019 \nmid 2^1 - 1, 2^2 - 1.$