Maths Olympiad Prep

Library / /22 of 27

Number theory Difficulty 6.8 National olympiad Prove it Austria

On a blackboard, there are 1717 integers not divisible by 1717. Alice and Bob play a game. Alice starts and they alternately play the following moves:
* Alice chooses a number aa on the blackboard and replaces it with a2a^2.
* Bob chooses a number bb on the blackboard and replaces it with b3b^3.

Alice wins if the sum of the numbers on the blackboard is a multiple of 1717 after a finite number of steps.

Prove that Alice has a winning strategy.

Solution

Since both the problem statement and the winning condition are given in terms of divisibility by 1717, it is sufficient to consider the numbers modulo 1717. In the beginning, all the remainders are different from zero and Alice wins if the sum modulo 1717 becomes zero.

The moves aa2a \mapsto a^2 and bb3b \mapsto b^3 turn remainders into powers of the original nonzero values. Therefore, Fermat's little theorem can be applied. For a≢0(mod17)a \not\equiv 0 \pmod{17} and the prime number 1717, one has
a161(mod17). a^{16} \equiv 1 \pmod{17}.
So if Alice squares the same number aa four times in a row, then the remainder 11 modulo 1717 is always obtained. Bob cannot do anything about it, because if Bob raises this number to the third power kk times, we get a result of
a23k=163k13k=1(mod17). a^{2 \cdot 3^k} = 16^{3^k} \equiv 1^{3^k} = 1 \pmod{17}.
The timing of Bob's moves does not matter, as the order of the factors in the exponent does not change anything.

Therefore, Alice can make all the remainders equal to 11 by squaring each number four times. Then of course the sum is 1710(mod17)17 \cdot 1 \equiv 0 \pmod{17} and Alice has won.

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 and solution reproduced as published; topic and difficulty added by this site.