Matematyka.pl

Weźmy takie \(\displaystyle{ b \in \mathbb{Z}}\), że \(\displaystyle{ ba \equiv -1 \pmod{p}}\). Na mocy Chińskiego Twierdzenia o Resztach układ

\(\displaystyle{ \begin{cases} n \equiv b \pmod {p} \\ n \equiv 1 \pmod{p-1} \end{cases}}\)

ma nieskończenie wiele rozwiązań \(\displaystyle{ n \in \mathbb{N}}\). Wystarczy wykazać, że każde z nich spełnia warunek zadania.

Na mocy Małego Mwierdzenia Fermata, kongruencja \(\displaystyle{ n \equiv 1 \pmod{p-1}}\) gwarantuje \(\displaystyle{ a^n \equiv a^1 \pmod{p}}\). Zatem dla każdego \(\displaystyle{ n}\) spełniającego układ kongruencji mamy

\(\displaystyle{ n \cdot a^n + 1 \equiv b \cdot a^1 + 1 \equiv 0 \pmod{p}}\),

co należało wykazać.