Question

найти остаток от деления числа a на m если a=15^254 m=17

Answer 1

При решении будем использовать замену одного числа эквивалентным ему по модулю 17, то есть дающим при делении на 17 тот же остаток.

$15^{254}\equiv(15-17)^{254}=(-2)^{254}=2^{254}=2^2\cdot2^{252}=4\cdot(2^4)^{63}=4\cdot16^{63}\equiv\\\equiv4\cdot(16-17)^{63}=4\cdot(-1)^{63}=4\cdot(-1)=-4\equiv-4+17=13\ (\mod 17)$