Question

Какой остаток при делении на 13 даёт число 3^70? Буду рада, если ответ будет с решением.

Answer 1

Ответ:

3:13=0.2307692308 70:13=5.3846153846

Answer 2

Для решения этой задачи, можно воспользоваться свойством остатка от деления степени числа. Заметим, что числа 3 и 13 взаимно простые, поэтому мы можем воспользоваться малой теоремой Ферма, которая гласит:

a^(p-1) ≡ 1 (mod p)

где a - целое число, p - простое число, и (mod p) обозначает остаток от деления на p.

В данной задаче, a = 3 и p = 13. Поскольку 13 - простое число, применяем малую теорему Ферма:

3^(13-1) ≡ 1 (mod 13)

3^12 ≡ 1 (mod 13)

Теперь мы можем выразить 3^70 в терминах 3^12:

3^70 = (3^12)^5 * 3^10

Заметим, что (3^12)^5 дает остаток 1 при делении на 13, согласно малой теореме Ферма:

(3^12)^5 ≡ 1^5 ≡ 1 (mod 13)

Теперь у нас остается только рассмотреть 3^10. Мы можем выразить его в терминах 3^12:

3^10 = (3^12)^10 * 3^(-2)

Здесь мы видим, что (3^12)^10 снова дает остаток 1 при делении на 13:

(3^12)^10 ≡ 1^10 ≡ 1 (mod 13)

Теперь у нас остается только 3^(-2). Чтобы выразить это в терминах 3^12, мы можем воспользоваться тем, что (3^12) * (3^(-12)) ≡ 1 (mod 13). Тогда:

3^(-2) ≡ (3^12) * (3^(-12)) * 3^(-2) ≡ 1 * (3^(-12)) * 3^(-2) ≡ (3^(-12)) * 3^(-2) (mod 13)

Теперь у нас осталось только узнать остаток от деления (3^(-12)) * 3^(-2) на 13.

Здесь нам поможет обратный элемент в кольце по модулю. Обратный элемент для 3 в кольце по модулю 13 равен 9, так как 3 * 9 ≡ 1 (mod 13).

Теперь мы можем подставить обратный элемент:

(3^(-12)) * 3^(-2) ≡ (9^12) * 9^2 ≡ 1 * 9^2 ≡ 81 ≡ 5 (mod 13)

Таким образом, остаток при делении числа 3^70 на 13 равен 5.