Question

Помогите найти  остаток от деления числа: 5^2013 на 13

Answer 1

Заметим, что 5^2 = 25 = 26 - 1 = 13*2 - 1

Тогда число 5^(2n) сравнимо по модулю 13 с числом (-1)^n (для доказательства достаточно раскрыть по биному (26 - 1)^n и заметить, что все слагаемые кроме (-1)^n делятся на 26)

Отсюда число 5^2012 = 26^1006 сравнимо по модулю 13 с числом (-1)^1006 = 1. А тогда число 5^2013 = 5 * 5^2012 при делении на 13 даёт остаток 5.