Математикадан 50-ші халықаралық олимпиада, 2009 жыл, Бремен

$\{ 1,\ldots ,n \}$ жиынынан әртүрлі ${{a}_{1}}$, $\ldots$, ${{a}_{k}}$ натурал сандары алынған; мұндағы $n$ — натурал сан және $k\ge 2$. Егер әрбір $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$ - противоречие.