IrMO 2011 Problem 3

The integers $a_0, a_1, a_2, a_3,\ldots$ are defined as follows: $a_0 = 1$ , $a_1 = 3$ , and $a_{n+1} = a_n + a_{n-1}$ for all $n \ge 1$ . Find all integers $n \ge 1$ for which $na_{n+1} + a_n$ and $na_n + a_{n-1}$ share a common factor greater than $1$ .