Processing math: 65%

50-я Международная Математическая Oлимпиада
Германия, Бремен, 2009 год


Даны целое положительное число n и попарно различные целые числа a1, , ak (k2) из множества {1,,n} такие, что для каждого i=1,,k1 число ai(ai+11) делится на n. Докажите, что число ak(a11) не делится на n.
посмотреть в олимпиаде

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

  7
2 года 1 месяца назад #

Предположим обратное. Пусть n=pα11pα22...pαss - разложение числа n на простые множители.

1)Если ai не делится на pαjj, тогда ai+11 делится pj, т.е. ai+1 не делится на pj. Следовательно ai+21 делится на pαjj. Аналогично продолжая это рассуждение, получаем, что 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 - противоречие.