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

Найдите все такие простые $p$, что существует бесконечно много натуральных $n$, удовлетворяющих $p|n^{ n+1}+(n+1)^n.$

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

Ответ: Для всех простых $p>2.$

Очевидно, что $p=2$ не подходит. Далее для любого $p>2$ докажем, что существует бесконечно много таких $n.$

Рассмотрим натуральные $n$ такие, что

$$n\equiv -2\pmod p,$$

$$n\equiv -1 \pmod {p-1}.$$

Очевидно эта система сравнений имеет бесконечно много решений из Китайской Теоремы об Остатках.

Теперь докажем, что для таких $n$ верна искомая делимость:

$$n^{n+1}+(n+1)^n\equiv (-2)^{n+1}+(-1)^{n}\equiv (-2)^{0}+(-1)^{-1}\equiv 1-1\equiv 0\pmod p.\quad\blacksquare$$