Question

Чему равен остаток от деления числа 159 ^191 на 1000?

Answer 1

1) 159^2 = 25281 при делении на 1000 дает остаток 281.
Дальше все знаки = означают "такой же остаток от деления на 1000".
159^191 = 159*159^190 = 159*(159^2)^95 = 159*281^95

2) 281^2 = 78961 = 961
159*281*281^94 = 44679*(281^2)^47 = 679*961^47 = 679*961*961^46

3) 961^2 = 923521 = 521
679*961*(961^2)^23 = 652519*521^23 = 519*521*521^22

4) 521^2 = 271441 = 441
519*521*(521^2)^11 = 270399*441^11 = 399*441*441^10

5) 441^2 = 194481 = 481
399*441*(441^2)^5 = 175959*481^5 = 959*481*481^4

6) 481^2 = 231361 = 361
959*481*(481^2)^2 = 461279*361^2 = 279*361^2

7) 361^2 = 130321 = 321
279*361^2 = 279*321 = 89559 = 559

Ответ: 559