50-я Международная Математическая OлимпиадаГермания, Бремен, 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$.

Комментарий/решение

Предположим обратное. Пусть $n=p_1^{\alpha_1}p_2^{\alpha_2}...p_s^{\alpha_s}$ - разложение числа $n$ на простые множители.

1)Если $a_i$ не делится на $p_j^{\alpha_j}$, тогда $a_{i+1}-1$ делится $p_j$, т.е. $a_{i+1}$ не делится на $p_j$. Следовательно $a_{i+2}-1$ делится на $p_j^{\alpha_j}$. Аналогично продолжая это рассуждение, получаем, что $a_{i}\equiv 1 \pmod {p_j^{\alpha_j}}$ для всех $i$.

2)Если $a_i$ делится на $p_j^{\alpha_j}$ для некоторого $i$, то $a_i$ делится на $p_j^{\alpha_j}$ для всех $i$(иначе предыдущий пункт противоречит этому)

3) $a_1\equiv a_2\equiv...\equiv a_k\pmod{ p_j^{\alpha_j}}$ для всех $j$. Откуда по китайской теореме об остатках они сравнимы между собой по модулю $n$ - противоречие.