Номер 30.44, страница 249 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 5. Основы теории делимости. Параграф 30. Простые и составные числа - номер 30.44, страница 249.

Условие.

30.44. Докажите, что $p^q + q^p \equiv (p+q) \pmod{pq}$, где $p$ и $q$ — различные простые числа.

Решение.

Чтобы доказать сравнение $p^q + q^p \equiv (p + q) \pmod{pq}$, где $p$ и $q$ — различные простые числа, достаточно доказать, что это сравнение выполняется по модулю $p$ и по модулю $q$ по отдельности. Если разность $(p^q + q^p) - (p + q)$ делится и на $p$, и на $q$, то, поскольку $p$ и $q$ взаимно просты, эта разность будет делиться и на их произведение $pq$.

1. Доказательство по модулю $p$.

Рассмотрим сравнение $p^q + q^p \equiv p + q \pmod{p}$.

Упростим левую и правую части этого сравнения.

Поскольку $p^q$ является степенью $p$ (с показателем $q \ge 2$, так как $q$ — простое число, отличное от $p$), то $p^q$ делится на $p$, следовательно $p^q \equiv 0 \pmod{p}$. Также очевидно, что $p \equiv 0 \pmod{p}$.

Подставив эти значения в сравнение, получим:

$0 + q^p \equiv 0 + q \pmod{p}$

$q^p \equiv q \pmod{p}$

Это сравнение верно согласно Малой теореме Ферма, которая утверждает, что для любого простого числа $p$ и любого целого числа $a$ выполняется $a^p \equiv a \pmod{p}$. В данном случае $a = q$.

Таким образом, мы доказали, что $p^q + q^p \equiv p + q \pmod{p}$.

2. Доказательство по модулю $q$.

Теперь рассмотрим сравнение $p^q + q^p \equiv p + q \pmod{q}$.

Действуя аналогично, упростим обе части.

Поскольку $q^p$ делится на $q$, то $q^p \equiv 0 \pmod{q}$. Также $q \equiv 0 \pmod{q}$.

Подставив эти значения, получим:

$p^q + 0 \equiv p + 0 \pmod{q}$

$p^q \equiv p \pmod{q}$

Это сравнение также верно по Малой теореме Ферма, примененной для простого числа $q$ и целого числа $p$.

Таким образом, мы доказали, что $p^q + q^p \equiv p + q \pmod{q}$.

Заключение.

Мы показали, что:

• выражение $(p^q + q^p) - (p + q)$ делится на $p$;
• выражение $(p^q + q^p) - (p + q)$ делится на $q$.

Так как $p$ и $q$ — различные простые числа, они являются взаимно простыми. Если целое число делится на два взаимно простых числа, то оно делится и на их произведение. Следовательно, $(p^q + q^p) - (p + q)$ делится на $pq$.

Это означает, что $p^q + q^p \equiv p + q \pmod{pq}$, что и требовалось доказать.

Ответ: Утверждение доказано.