По малой теореме Ферма: $q^{p-1} \equiv 1 \pm od{p}$ и $p^{q-1} \equiv 0 \pm od{p}$, значит $p^{q-1} + q^{p-1} \equiv 1 \pm od{p}$. Аналогично: $p^{q-1} \equiv 1 \pm od{q}$ и $q^{p-1} \equiv 0 \pm od{q}$, значит $p^{q-1} + q^{p-1} \equiv 1 \pm od{q}$. Так как $p$ и $q$ взаимно просты и оба делят $(p^{q-1} + q^{p-1} - 1)$, то $pq \mid p^{q-1} + q^{p-1} - 1$, то есть $p^{q-1} + q^{p-1} \equiv 1 \pm od{pq}$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!