докажите, что если целые числа a и b при делении на натуральное число n дают равные остатки, то числа a^m и b^m, где m принадлежит натуральным числам, при делении на n также дают равные остатки. Используя этот вывод, найдите остаток от деления 3^129 на 8

Привет! Давай разберем эту интересную задачу по шагам. 1. Доказательство

Нам дано, что числа $a$ и $b$ при делении на $n$ дают одинаковые остатки. Это значит, что мы можем записать:

$$a = nq_1 + r$$ $$b = nq_2 + r$$

где $q_1$ и $q_2$ – это частные от деления $a$ и $b$ на $n$ соответственно, а $r$ – общий остаток.

Теперь рассмотрим разность $a - b$:

$$a - b = (nq_1 + r) - (nq_2 + r) = nq_1 - nq_2 = n(q_1 - q_2)$$

Это означает, что $a - b$ делится на $n$ без остатка.

Теперь докажем, что $a^m - b^m$ тоже делится на $n$. Вспомним формулу разности степеней:

$$a^m - b^m = (a - b)(a^{m-1} + a^{m-2}b + a^{m-3}b^2 + ... + ab^{m-2} + b^{m-1})$$

Мы уже знаем, что $(a - b)$ делится на $n$. Значит, и вся правая часть выражения делится на $n$, так как один из множителей делится на $n$. Таким образом, $a^m - b^m$ делится на $n$.

Если $a^m - b^m$ делится на $n$, то это означает, что $a^m$ и $b^m$ дают одинаковые остатки при делении на $n$. Что и требовалось доказать.

2. Нахождение остатка от деления $3^{129}$ на $8$

Заметим, что $3$ при делении на $8$ дает остаток $3$. Теперь нам нужно найти такое число, которое было бы близко к $3^{129}$ и при этом легко делилось на $8$.

Давай посмотрим на степени числа $3$ по модулю $8$:

$$3^1 \equiv 3 \pmod{8}$$ $$3^2 = 9 \equiv 1 \pmod{8}$$

Здесь мы видим, что $3^2$ дает остаток $1$ при делении на $8$. Это очень удобно, потому что единицу возводить в любую степень легко.

Теперь представим $3^{129}$ как $3^{2 \cdot 64 + 1}$:

$$3^{129} = 3^{2 \cdot 64 + 1} = (3^2)^{64} \cdot 3^1 = 9^{64} \cdot 3$$

Так как $9 \equiv 1 \pmod{8}$, то:

$$9^{64} \equiv 1^{64} \equiv 1 \pmod{8}$$

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

$$3^{129} = 9^{64} \cdot 3 \equiv 1 \cdot 3 \equiv 3 \pmod{8}$$

Значит, остаток от деления $3^{129}$ на $8$ равен $3$.

Ответ: Остаток от деления $3^{129}$ на $8$ равен $3$.