Question

Пожалуйста срочно Найти остаток (3^100):21 и (2^100):23

Answer 1

3*100=300
300/21=142 без остатка

2*100=200
200/23=0,8 остаток 16

Answer 2

Для нахождения остатка от деления больших чисел на другие числа, можно использовать свойства арифметики остатков.

1. Для (3^100) : 21: Заметим, что 21 = 3 * 7, а также что (3^100) можно представить как (3^2)^50, то есть 3 в степени 100 равно (3^2)^50.

Теперь используем малую теорему Ферма: Если p - простое число и a - целое число, не делящееся на p, то a^(p-1) при делении на p даёт остаток 1.

Так как 7 - простое число, то применяя малую теорему Ферма, получим: (3^100) : 7 ≡ 1 (mod 7)

Также заметим, что (3^100) : 3 = (3^99), то есть деление на 3 соответствует вычитанию степени 1. Таким образом: (3^100) : 3 ≡ (3^99) ≡ (3^98) ≡ ... ≡ 1 (mod 3)

Теперь найдем остатки (3^100) : 21: (3^100) : 21 = ( (3^100) : 3 ) : 7 ≡ 1 : 7 ≡ 1 (mod 21)

Ответ: остаток от деления (3^100) на 21 равен 1.

2. Для (2^100) : 23: Также как и в предыдущем случае, применим малую теорему Ферма для простого числа 23: (2^100) : 23 ≡ 1 (mod 23)

Ответ: остаток от деления (2^100) на 23 равен 1.