Упр.30.44 ГДЗ Мерзляк Поляков 8 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Мерзляк, Поляков 8 класс, Вентана-Граф: 30.44. Докажите, что p^q +q^p ? (p+q) (mod pq), где p и q — различные простые числа.

По малой теореме Ферма имеем:

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

Тогда

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

Умножим первое сравнение на $$p$$, а второе — на $$q$$:

$$p^q-p \equiv 0 \pmod q,\qquad q^p-q \equiv 0 \pmod p.$$

Так как $$p$$ и $$q$$ — различные простые числа, то $$p$$ делит $$q^p-q$$, а $$q$$ делит $$p^q-p$$. Следовательно, оба числа делятся на $$pq$$:

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

Складывая эти сравнения, получаем:

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

Значит,

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

Ответ

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