Найти бесконечно много решений

[rightways]

Дано натуральное число $a$. Докажите, что для любого натурального $m$ существует бесконечно много натуральных $n$ таких, что количество делителей числа $na^n+1$ делится на $m$.

[rightways]

Эта задача предлагалась как первая задача национальной олимпиады.

[lopkityu]

Пусть $ p $ - простое, $ (a, p)=1 $. Докажем индукцией по $ m $, что $ \forall m\geq 1 \exists n: p^{m}|na^{n}+1 $. База очевидна, поскольку, положив $ n=p-1 $, имеем $ (p-1)a^{p-1} \equiv -1(\bmod p) $. Пусть теперь $ p_{k} $ такое, что $ p_{k}a^{p_{k}} \equiv -1(\bmod p^{k}) $. Рассмотрим числа вида $ a_{i}=(i(p^{k+1}-p^{k})+p_{k})a^{i(p^{k+1}-p^{k})+p_{k}}, 0\leq i\leq p-1 $. По теореме Эйлера $ a^{p^{k+1}-p^{k}} \equiv 1(\bmod p^{k+1}) $, откуда $ a^{i(p^{k+1}-p^{k})+p_{k}} \equiv a^{p_{k}}(\bmod p^{k+1}) $. Кроме того $ a_{i} \equiv p_{k}a^{p_{k}} \equiv -1(\bmod p^{k}) $, потому каждое $ a_{i} $ при делении на $ p^{k+1} $ может давать только остаток вида $ bp^{k}-1, 1\leq b\leq p $, которых ровно $ p $ штук. С другой стороны, допустив, что $ a_{i} \equiv a_{j}(\bmod p^{k+1}) $ для некоторых $ i\neq j $, приходим к тому, что $ ip^{k} \equiv jp^{k}(\bmod p^{k+1}) $, что невозможно. Так как наших $ a_{i} $ тоже ровно $ p $ штук, то они должны давать все допустимые остатки, откуда вытекает существование такого $ p_{k+1} $, что $ p_{k+1}a^{p_{k+1}} \equiv -1(\bmod p^{k+1}) $, что завершает доказательство. Осталось отметить, что, как следует из вышеизложенного, для любого $ m $ существует бесконечно много таких $ n $, что $ p^{m-1}|na^{n}+1 $, но $ p^{m}\nmid na^{n}+1 $, откуда по формуле количества делителей следует утверждение задачи.