2^125 mod 127? Помогите решить. Помогите решить

Answer 1

я вижу такое решение, но, вероятно, кто-то знает лучше:

128=2^7

2^125= (2^7) ^17*2^6=128^17*64= (127^17*64
 (127^17 разложим по биному Ньютона.
каждое слагаемое будет кратно 127 кроме последнего, которое=1
 (127^17*64 каждое слагаемое будет кратно 127, кроме последнего-
оно будет=64.

ответ 64

Answer 2

127 - простое число, это же поле вычетов получается. Оно является коммутативной группой по умножению по простому модулю, за исключением нуля, в ней 127 - 1 = 126 элементов. Откуда имем:
2^126 mod 127 = 1 = (2x) mod 127 = 1 = x = 64.