Олимпиада Туймаада по математике. Младшая лига. 2006 год

Даны 10 различных нечетных простых чисел. Может ли так случиться, что разность шестнадцатых степеней любых двух из них делится на любое из оставшихся чисел? ( Ф. Петров, К. Сухов )

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

Пусть $p$ наибольшее из этих простых. Тогда разность $16$ степеней любых двух их оставшихся чисел делиться на $p$. Если $p | a^{16}-b^{16} \Rightarrow a^8 \equiv b^8$ или $a^8 \equiv -b^8$. То есть всего возможно $2$ остатка для $8$ степени. Так как оставшихся чисел $9$, то среди них есть $5$, которые дают одинаковый остаток в $8$ степени по модулю $p$. Аналогично получаем, что есть $3$ числа которые в $4$ степени дают одинаковый остаток по модулю $p$. Применяя те же рассуждения получаем, что есть такие $a, b$, что $p | a^2-b^2=(a-b)(a+b)$. Так как $p>a,b \Rightarrow p>a-b$. Значит $p|a+b$. Но $2|a+b$ и $2p>a+b$, противоречие. Значит таких простых нет.