Упр.30.44 ГДЗ Мерзляк Поляков 8 класс (Алгебра)
Мерзляк, Поляков
8 класс
Класс
8
Предмет
Алгебра
Автор
Мерзляк, Поляков
Упр.30.44 ГДЗ Мерзляк Поляков 8 класс (Алгебра)
Задача
Докажите, что $$p^q+q^p\equiv p+q\pmod{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}.$$
Другие учебники
Другие предметы








