Library / Austria competition problems /26 of 39

Austria competition problems, 2014

Number theory Difficulty 6.2 National Olympiad Prove it Austria

The sequence $\langle a_n \rangle$ is defined by the recursion
$a_{n+1} = 5a_n^6 + 3a_{n-1}^3 + a_{n-2}^2 \quad \text{for } n \ge 2$
and the set of starting values $\{a_0, a_1, a_2\} = \{2013, 2014, 2015\}$ .
(i.e., the starting values are these three numbers in arbitrary order.)
Show that the sequence does not contain any sixth power of an integer.

Solution

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 \neq 0 \bmod 7

and

a_i \neq 1 \bmod 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}

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 \bmod 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$

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.