计算大数的模数

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)。

Calculating the modulus of a large number