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

Глава 5. Основы теории делимости. Параграф 27. Деление с остатком. Сравнения по модулю и их свойства - номер 27.33, страница 227.

Условие.

27.33. Найдите остаток при делении числа $m$ на число $n$, если:

1) $m = 11^{43}$, $n = 7$;

2) $m = 13^{52}$, $n = 17$;

3) $m = 3^{30}$, $n = 31$.

Решение.

1) $m = 114^{43}, n = 7$

Для решения этой задачи воспользуемся свойствами сравнений по модулю и малой теоремой Ферма. Малая теорема Ферма утверждает, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, выполняется сравнение: $a^{p-1} \equiv 1 \pmod p$.

Сначала найдем остаток от деления основания степени $114$ на $7$:
$114 = 7 \cdot 16 + 2$.
Следовательно, $114 \equiv 2 \pmod 7$.

Это означает, что $114^{43}$ дает такой же остаток при делении на $7$, как и $2^{43}$:
$114^{43} \equiv 2^{43} \pmod 7$.

Теперь применим малую теорему Ферма для $p=7$. Так как $7$ — простое число и $2$ не делится на $7$, то:
$2^{7-1} \equiv 2^6 \equiv 1 \pmod 7$.

Используем это свойство для упрощения степени $43$. Представим показатель $43$ в виде $43 = 6 \cdot k + r$:
$43 = 6 \cdot 7 + 1$.

Тогда:
$2^{43} = 2^{6 \cdot 7 + 1} = (2^6)^7 \cdot 2^1$.

Найдем остаток от деления этого выражения на $7$:
$(2^6)^7 \cdot 2^1 \equiv 1^7 \cdot 2 \pmod 7 \equiv 1 \cdot 2 \pmod 7 \equiv 2 \pmod 7$.

Таким образом, остаток от деления числа $114^{43}$ на $7$ равен $2$.
Ответ: $2$

2) $m = 135^{52}, n = 17$

Сначала найдем остаток от деления $135$ на $17$:
$135 = 17 \cdot 8 - 1$, следовательно, $135 \equiv -1 \pmod{17}$.

Теперь мы можем найти остаток для $135^{52}$:
$135^{52} \equiv (-1)^{52} \pmod{17}$.

Так как показатель степени $52$ — чётное число, то $(-1)^{52} = 1$.
Значит, $135^{52} \equiv 1 \pmod{17}$.

Остаток от деления числа $135^{52}$ на $17$ равен $1$.
Ответ: $1$

3) $m = 3^{30}, n = 31$

В этом случае мы можем напрямую применить малую теорему Ферма, которая гласит, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, выполняется сравнение: $a^{p-1} \equiv 1 \pmod p$.

Здесь $p=31$ — простое число, а основание степени $a=3$ не делится на $31$.

Подставляя наши значения в теорему, получаем:
$3^{31-1} \equiv 3^{30} \equiv 1 \pmod{31}$.

Таким образом, остаток от деления числа $3^{30}$ на $31$ равен $1$.
Ответ: $1$