IMO олимпиада по математике 2009 года | Казахстанские олимпиады

Даны целое положительное число $n$ и попарно различные целые числа ${{a}_{1}}$, $\ldots$, ${{a}_{k}}$ ($k\ge 2$) из множества $\left\{ 1,\ldots ,n \right\}$ такие, что для каждого $i=1,\ldots ,k-1$ число ${{a}_{i}}\left( {{a}_{i+1}}-1 \right)$ делится на $n$. Докажите, что число ${{a}_{k}}\left( {{a}_{1}}-1 \right)$ не делится на $n$.