Question

Сколько будет 2 в сотой степени (mod 3)?

Answer 1

2^100, сколько же ещё?

Answer 2

Чтобы найти значение числа 2 в степени 100 (mod 3), мы должны последовательно возводить число 2 в квадрат и находить остаток от деления на 3.

2^1 (mod 3) = 2 2^2 (mod 3) = 4 (остаток от деления на 3 = 1) 2^3 (mod 3) = 8 (остаток от деления на 3 = 2) 2^4 (mod 3) = 16 (остаток от деления на 3 = 1) 2^5 (mod 3) = 32 (остаток от деления на 3 = 2)

Мы видим, что остатки от деления на 3 чередуются между 1 и 2 при каждом возведении числа 2 в степень. Поэтому, чтобы найти остаток от деления числа 2 в степени 100 на 3, нам достаточно знать, четное ли это число или нет.

Так как 100 - четное число, остаток от деления числа 2 в степени 100 на 3 будет таким же, как остаток от деления числа 2 в степени 2 на 3.

2^2 (mod 3) = 4 (остаток от деления на 3 = 1)

Таким образом, 2 в сотой степени (mod 3) равно 1.