International Mathematical Olympiad 2009 Problem 1

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