Найдите остаток от деления числа 1000^2016 на 13.

Предыдущий
вопрос Следующий
вопрос

Для нахождения остатка от деления числа (1000^{2016}) на 13, можно воспользоваться малой теоремой Ферма.

По теореме Ферма, если (p) - простое число и (a) - целое число, не кратное (p), то (a^{p-1} \equiv 1 \pmod{p}).

Так как 13 - простое число, то (1000^{12} \equiv 1 \pmod{13}) по теореме Ферма.

Теперь мы можем выразить (1000^{2016}) как ((1000^{12})^{168} \times 1000^{12}). Так как ((1000^{12})^{168} \equiv 1 \pmod{13}) и (1000^{12} \equiv (-1)^{12} \equiv 1 \pmod{13}), то в итоге получаем, что (1000^{2016} \equiv 1 \times 1 \equiv 1 \pmod{13}).

Следовательно, остаток от деления числа (1000^{2016}) на 13 равен 1.