Номер 47.25, страница 366 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

47.25. Найдите остаток при делении числа $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$ воспользуемся свойствами сравнений по модулю и малой теоремой Ферма.

Сначала найдем остаток от деления основания степени, числа 114, на 7:

$114 = 7 \cdot 16 + 2$.

Это означает, что 114 дает такой же остаток при делении на 7, что и число 2. В терминах сравнений это записывается как $114 \equiv 2 \pmod{7}$.

Согласно свойству сравнений, мы можем заменить основание степени на его остаток:

$114^{43} \equiv 2^{43} \pmod{7}$.

Теперь задача сводится к нахождению остатка от деления $2^{43}$ на 7. Поскольку 7 — простое число, а 2 не делится на 7, мы можем применить малую теорему Ферма, которая гласит, что $a^{p-1} \equiv 1 \pmod{p}$ для любого простого $p$ и целого $a$, не кратного $p$.

В нашем случае $a=2$ и $p=7$, поэтому:

$2^{7-1} \equiv 1 \pmod{7}$, то есть $2^6 \equiv 1 \pmod{7}$.

Теперь представим показатель степени 43 через 6:

$43 = 6 \cdot 7 + 1$.

Подставим это в наше выражение:

$2^{43} = 2^{6 \cdot 7 + 1} = (2^6)^7 \cdot 2^1$.

Используя найденное ранее сравнение $2^6 \equiv 1 \pmod{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 = 13^{52}$ на число $n=17$.

Число 17 — простое, а 13 не делится на 17. Снова воспользуемся малой теоремой Ферма: $a^{p-1} \equiv 1 \pmod{p}$.

Для $a=13$ и $p=17$ имеем:

$13^{17-1} \equiv 1 \pmod{17}$, то есть $13^{16} \equiv 1 \pmod{17}$.

Представим показатель степени 52 через 16:

$52 = 16 \cdot 3 + 4$.

Тогда:

$13^{52} = 13^{16 \cdot 3 + 4} = (13^{16})^3 \cdot 13^4$.

По свойствам сравнений:

$(13^{16})^3 \cdot 13^4 \equiv 1^3 \cdot 13^4 \pmod{17} \equiv 13^4 \pmod{17}$.

Осталось вычислить $13^4 \pmod{17}$. Для удобства вычислений заметим, что $13 = 17 - 4$, следовательно, $13 \equiv -4 \pmod{17}$.

Тогда:

$13^4 \equiv (-4)^4 \pmod{17}$.

$(-4)^4 = 4^4 = (4^2)^2 = 16^2$.

Так как $16 = 17 - 1$, то $16 \equiv -1 \pmod{17}$.

Следовательно:

$16^2 \equiv (-1)^2 \pmod{17} \equiv 1 \pmod{17}$.

Значит, остаток при делении $13^{52}$ на 17 равен 1.

Ответ: 1

3) Найдем остаток при делении числа $m = 3^{30}$ на число $n=31$.

Число 31 — простое, а 3 на 31 не делится. Это идеальные условия для применения малой теоремы Ферма: $a^{p-1} \equiv 1 \pmod{p}$.

В нашем случае $a=3$ и $p=31$.

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

$3^{31-1} \equiv 1 \pmod{31}$, то есть $3^{30} \equiv 1 \pmod{31}$.

Это сравнение напрямую показывает, что остаток от деления $3^{30}$ на 31 равен 1.

Ответ: 1