Integers $ a_1,a_2,\ldots a_9$ satisfy the relations $ a_{k+1}=a_k^3+a_k^2+a_k+2$ for $ k=1,2,...,8$. Prove that among these numbers there exist three with a common divisor greater than $ 1$.
Problem
Source: Moldova NMO 2002 grade 9 problem nr.5
Tags: modular arithmetic
Rofler
03.11.2008 02:59
mod 5, 5->2->1 3->1 4->1 Easy to show 3 are $ \equiv 0$ mod 5
vinskman
03.11.2008 06:08
rofler's representations:
$ \text{when}$
$ a_1\equiv 0\pmod 5 , \implies a_2\equiv 2\pmod 5 \implies a_3\equiv 1\pmod 5$ $ \implies a_4\equiv 0\pmod 5\implies a_5\equiv 2\pmod 5\implies a_6\equiv 1\pmod 5$
$ \implies a_7\equiv 0\pmod 5 , \text {i.e. } a_1,a_4,a_7 \text{has common factor 5}$
$ \text{when}$
$ a_1\equiv 1\pmod 5 , \text {in brief } 1 \to 0 \to 2 \to 1 \to 0 \to 2 \to 1 \to 0 , \text {i.e. } a_2,a_5,a_8 \text{has common factor 5}$
$ \text{when}$
$ a_1\equiv 2\pmod 5 , \text {in brief } 2 \to 1 \to 0 \to 2 \to 1 \to 0 \to 2 \to 1\to 0 , \text {i.e. } a_3,a_6,a_9 \text{has common factor 5}$
$ \text{when}$
$ a_1\equiv 3\pmod 5 , \text {in brief } 3 \to 1 \to 0 \to 2 \to 1\to 0 \to 2 \to 1 \to 0 ,\text {i.e. } a_3,a_6,a_9 \text{has common factor 5}$
$ \text{when}$
$ a_1\equiv 4\pmod 5 , \text {in brief } 4 \to 1 \to 0 \to 2 \to 1\to 0 \to 2 \to 1 \to 0 ,\text {i.e. } a_3,a_6,a_9 \text{has common factor 5}$