Question

Найти остаток от деления 327³²+151¹⁸¹ на 29

Answer 1

Ответ: 12

327³²+151¹⁸¹≡8³²+6¹⁸¹(mod 29)=64¹⁶+6*36⁹⁰≡6¹⁶+6*7⁹⁰(mod 29)=36⁸+6*49⁴⁵≡7⁸+6*20⁴⁵(mod 29)=49⁴+6*8000¹⁵≡20⁴+6*25¹⁵(mod 29)=400²+150*625⁷≡23²+5*16⁷(mod 29)=529+80*256³≡7+22*24³(mod 29)=7+528*576≡7+6*25(mod 29)=157≡12(mod 29)

______________

В решении использованы свойства сравнения чисел по модулю

Answer 2

Для нахождения остатка от деления числа на другое число, можно использовать операцию модуля (%).

Давайте найдем остаток от деления выражения 327³² + 151¹⁸¹ на 29:

1. Вычислим значение выражения 327³² + 151¹⁸¹: 327³² = 327 * 327 * ... * 327 (32 раза) = огромное число 151¹⁸¹ = 151 * 151 * ... * 151 (181 раз) = тоже огромное число

2. Поскольку значения этих чисел слишком большие, вычислить их напрямую будет трудно и неэффективно.

Вместо этого воспользуемся малой теоремой Ферма: если p - простое число, а a - целое число не кратное p, тогда a^(p-1) ≡ 1 (mod p).

В нашем случае p = 29 (простое число), поэтому можем упростить выражение:

327³² ≡ 1 (mod 29) (по малой теореме Ферма) 151¹⁸¹ ≡ 1 (mod 29) (по малой теореме Ферма)

Теперь, остаток от деления суммы этих чисел на 29:

(327³² + 151¹⁸¹) % 29 ≡ (1 + 1) % 29 ≡ 2 % 29 ≡ 2

Таким образом, остаток от деления выражения 327³² + 151¹⁸¹ на 29 равен 2.