Математикадан 44-ші халықаралық олимпиада, 2003 жыл, Токио

$p$ саны жай сан болсын. Кез келген $n$ натурал саны үшін ${{n}^{p}}-p$ саны $q$ санына бөлінбейтіндей $q$ жай саны табылатынын дәлелдеңіздер.

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

Допустим не существует тогда число $n^p-p=p^{a_1}_1*....*p^{a_x}_x$ по МТФ $n^p-p\equiv 0,p \pmod {p}$

Пусть $n^p-p \equiv 0 \pmod {p}$$\Rightarrow$$n=px$ Заметим $x=p^{l_1}_c*....*p^{l_v}_v+c$ где $n>p^{l_1}_c,....,p^{l_v}_{v+c}$

$\Rightarrow$ $n^p-p \ne \equiv 0 \pmod {z}$ где $z$ умножение нескольких простых чисел из набора $p^{a_1}_1*....*p^{a_x}_x$

$n^p-p\equiv n\pmod {p}$ Заметим что обязательно $p>n^p-p$ а иначе $q=p$ и все

$2p>n^p\Rightarrow \sqrt[p]{2p}>n$

Заметим что $2>\sqrt[a]{a}$

$3>\sqrt[p]{p}*\sqrt[p]{2}=\sqrt[p]{2p}>n$

$1)n=1,2)n=2$

Случай $1)$ невозможен

Случай $2)$ тоже легко проверить

Осталось проверить случай где $n$ неотриц

Ваше решение не верно

Во первых вы в самом начале берете: $n^p-p\equiv 0,p \pmod {p}$ как факт, если такого числа не существует

Что далеко не является фактом

В продолжении вы разобрали случай:

$n^p-p\equiv 0,p \pmod {p}$

Что эронично ведь в начале вы взяли это как факт

Во второй половине решения случай:

$n^p-p\equiv n\pmod {p}$

Но почему из этого следует что при $p=q$

$q \mid n^p-p$

Это не является фактом

Так как изначальное:

$n^p-p\equiv 0,p \pmod {p}$

Не является фактом

Рассмотрим простые делители числа: $X=\frac{p^p-1}{p-1}$.

Очевидно все они дают остаток $1$ при делении на $p$. Допустим, что все они дают остаток $1$ при делении на $p^2$. Так как, число $X$ произведение таких простых, то $X\equiv 1 \pmod{p^2}$. То есть $p^p-p \equiv 0 \pmod{p^2}$, что невозможно. Тогда существует $q \in \mathbb{P}$, что $q$ $\mid$ $X$, и $q \not\equiv 1 \pmod{p^2}$. Докажем, что $q$ подходит. Если:

$$n^p \equiv p \pmod{q} \Longrightarrow n^{p^2} \equiv p^p \equiv 1 \pmod{q}$$. Очевидно $n-1$ и $n^p-1$ не делятся на $q$. То есть $p^2$ показатель $mod$ $q$. Тогда $q-1$ $\vdots$ $p^2$ что невозможно.