Областная олимпиада по математике, 2007 год, 11 класс

Пусть $n$ — натуральное число, $p$ — простое, причем $(n+1)^p-n^p$ делится на некоторое натуральное число $q$. Докажите, что $(q-1)$ делится на $p$.

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

Пусть $q_1$ произвольный простой делитель числа $q$, тогда $(n+1)^p \equiv n^p$ $mod$ $q_1$, и так как $(n,n+1)=1$ $$\left(\frac{n+1}{n}\right)^p \equiv 1 \, mod \, q_1$$

Но, из МТФ следует, что $\left(\frac{n+1}{n}\right)^{q_1-1} \equiv 1 \, mod \, q_1$. Значит $p | q_1-1$. Тогда каждый простой делитель $q$ будет $q_1 \equiv 1$ $mod$ $p$, откуда $q \equiv 1 \, mod \, p$