Austria 2014

We consider second, third and sixth powers modulo 7:

x	$x^2$	$x^3$	$x^6$
0	0	0	0
1	1	1	1
2	4	1	1
3	2	6	1
4	2	1	1
5	4	6	1
6	1	6	1

In order to show that no element of the sequence is a sixth power, it is sufficient to show that no such element is congruent to 0 or 1 modulo 7. We prove this by induction. We wish to prove: $a_i\ne 0\mathrm{mod}7$ and $a_i\ne 1\mathrm{mod}7$ for all indices $i$. We can start the induction by noting that the values for the first three elements of the sequence modulo 7 are $2013\equiv 4$, $2014\equiv 5$ and $2013\equiv 6$. We now wish to show that the assumption "none of the elements $a_i$, $a_{i-1}$ or $a_{i-2}$ is congruent to 0 or 1 modulo 7" implies "$a_{i+1}$ is not congruent to 0 or 1 modulo 7" for all indices $i\ge 2$.

By definition of the sequence, we have $a_{i+1}=5a_i^6+3a_{i-1}^3+a_{i-2}^2$. By the assumption of the induction, we know that $5a_i^6\equiv 5\mathrm{mod}7$ holds. The second expression in the sum, $3a_{i-1}^3$, can only assume the values 3 or 4 modulo 7 (since $a_{i-1}$ can only take on the values from 2 through 6 modulo 7, and a third power of this can therefore only assume the values 1 or 6). By the same argument, the final expression in the sum, $a_{i-2}^2$, can only assume the values 1, 2 or 4. Summing all possible values, we see that $a_{i+1}$ can only be congruent to 2, 3, 4, 5 or 6 modulo 7, which completes the induction. $\square$