50-я Международная Математическая Oлимпиада
Германия, Бремен, 2009 год
Даны целое положительное число n и попарно различные целые числа a1, …, ak (k≥2) из множества {1,…,n} такие, что для каждого i=1,…,k−1 число ai(ai+1−1) делится на n. Докажите, что число ak(a1−1) не делится на n.
посмотреть в олимпиаде
Комментарий/решение:
Предположим обратное. Пусть n=pα11pα22...pαss - разложение числа n на простые множители.
1)Если ai не делится на pαjj, тогда ai+1−1 делится pj, т.е. ai+1 не делится на pj. Следовательно ai+2−1 делится на 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 - противоречие.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.