Найдите остаток числа 2 (в степени 2013) + 1 при делении ** 17

Question

Найдите остаток числа 2 (в степени 2013) + 1 при делении на 17

Answer 1

Рассмотрим остатки от деления на 17 степеней двойки:

2^0 mod 17 = 1

2^1 mod 17 = 2

2^2 mod 17 = 4

2^3 mod 17 = 8

2^4 mod 17 = 16

2^5 mod 17 = 15

2^6 mod 17 = 13

2^7 mod 17 = 9

2^8 mod 17 = 1

2^9 mod 17 = 2

2^10 mod 17 = 4

2^11 mod 17 = 8

2^12 mod 17 = 16

2^13 mod 17 = 15

2^14 mod 17 = 13

2^15 mod 17 = 9

2^16 mod 17 = 1

2^17 mod 17 = 2

...

Видно, что они циклические. Тогда, (2^2013 + 1) mod 17 = (2^(2013 mod 8) + 1) mod 17 = (2^5 + 1) mod 17 = 16