Расчет модуля большого количества

Question

Я изучаю викторину в дискретных структурах. Как я могу рассчитать 2^50 (mod5)? Я могу вычислить результат с меньшими числами с помощью калькулятора, но я не могу сделать это с большим количеством.

Answer 1

Предположим, у нас есть номер N = 5X + Y, где N, X и Y - целые числа (то есть N mod 5 = Y). Затем следует, что с 2N = 2(5X + Y) = 10x + 2Y, что 2N mod 5 = 2Y mod 5.

, подобным образом, так как 2^50 может быть переписано в виде ((2^5)^5)^2:

2^50 mod 5 = ((2^5 mod 5)^5 mod 5)^2 mod 5

2^50 mod 5 = ((2)^5 mod 5)^2 mod 5

2^50 mod 5 = (2)^2 mod 5

2^50 mod 5 = 4

Answer 2

Вы можете использовать тот факт, что if (2^x = t)(mod A) then (2^(x*y) = t^y)(mod A).

Таким образом, мы имеем:

2^2 = (-1) (mod 5) which means 
2^50 = (-1)^25(mod 5) 
    = -1 (mod 5) (which is the same as 4 (mod 5)) 

Использование фактического расчета, мы видим 2^50 = 1125899906842624 = -1(mod 5).