Упр.49.26 ГДЗ Мерзляк 10 класс Углубленный уровень (Алгебра)

Рассмотрим вариант решения задания из учебника Мерзляк, Номировский, Поляков 10 класс, Просвещение: 49.26. Докажите, что p^q+q^p?(p+q)(mod pq), где р и q — различные простые числа.

По малой теореме Ферма, так как $$p$$ и $$q$$ — различные простые числа, имеем:

$$p^{q-1}\equiv 1 \pmod q,$$

значит,

$$p^q-p=p\bigl(p^{q-1}-1\bigr)$$

делится на $$q$$, то есть

$$p^q\equiv p \pmod q.$$

Аналогично:

$$q^{p-1}\equiv 1 \pmod p,$$

значит,

$$q^p-q=q\bigl(q^{p-1}-1\bigr)$$

делится на $$p$$, то есть

$$q^p\equiv q \pmod p.$$

Следовательно, число $$p^q-p$$ делится на $$q$$, а число $$q^p-q$$ делится на $$p$$. Тогда сумма

$$p^q-p+q^p-q$$

делится и на $$p$$, и на $$q$$. Так как $$p$$ и $$q$$ — различные простые числа, то их произведение $$pq$$ делит эту сумму:

$$p^q-p+q^p-q\equiv 0 \pmod{pq}.$$

Отсюда

$$p^q+q^p\equiv p+q \pmod{pq}.$$

Ответ

$$p^q+q^p\equiv p+q \pmod{pq}.$$