modulus - 全等整数和模数

Question

我是这里的主题新手：/谁能告诉我如何解决以下问题？证明 36^2004 + 17^768 x 27^412 可以被 19 整除。谢谢！

Answer 1

可以使用简单的身份来解决上述问题，其中重要的是：

(a + b) mod c = a mod c + b mod c

还，

ab mod c = (a mod c)*(b mod c)

这也可用于求解非常大的指数，例如，如果您要求解：

24^3100 mod 19

您可能可以将其分解为：

24^(310*100) mod 19

可以进一步写成：

24^310 mod 19 x 24^100 mod 19

您可以进一步将其分解为您可以实际计算和解决的值。例如，如果你继续分解 100，你最终可能会解决

(24^4 mod 19)^25

等等等等。由于这是一个家庭作业问题，我只能提供提示而不是完整的解决方案。

您也可以使用快速取幂方法来做到这一点，其中指数以 2 的幂表示。