Западно-Китайская математическая олимпиада, 2013 год

Найдите все натуральные $a$ такие, что для любого натурального $n\ge 5$ верно $2^n-n^2\mid a^n-n^a$.

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

Ответ:$a=4; a=2$. Будем считать, что $a$ не меньше $2$. Рассмотрим нечетное простое число $p$. Тогда при $n=p-1$, получим, что $2^n-n^2 \equiv 0 \pmod {p}$.

Значит $a^{p-1} - (p-1)^a \equiv 0 \pmod {p}$. Возьмем $p$ таким, что $a$ делиться на $p$. Если $a$ не степень $2$, то такой выбор возможен, а значит получим, что $(-1)^a \equiv 0 \pmod p$. Значит $a=2^k$, для некоторого $k \geq 2$. Подставим: $2^{kn}-n^{2^k}\equiv 0 \pmod {2^n-n^2}$. Возьмем $n$ нечётным. $(n^2)^{k}\equiv (2^n)^{k} \pmod {2^n-n^2}$. Тогда $n^{2k}\equiv n^{2^{k}} \pmod {2^n-n^2}$. Поскольку $(n, 2^n-n^2)=(n, 2^n)=1$, то $n^{2^k-2k} \equiv 1 \pmod {2^n-n^2}$. Поскольку степенная функция растет быстрее многочлена, то для некоторого $n$, будет верно следующее неравенство: $2^n> n^{2^k-2k} -1 + n^2$. Что значит $2^k=2k$, откуда следует, что $k=1, k=2$. $a=4, a=2$