IMO 2009 Problem 1

Let $n$ be a positive integer and let $a_1, \dots, a_k$ ($k \ge 2$) be distinct integers in the set $\{1, \dots, n\}$ such that $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1, \dots, k-1$. Prove that $n$ does not divide $a_k(a_1 - 1)$.