计算pow(45,60)mod 61

Question

这是一个家庭作业问题.

我需要计算45 ^ 60 mod 61.我想知道任何快速方法以编程方式或手动方式获得结果,无论哪个更快.

Answer 1

由于费马的小定理,结果将是1

如果p是素数.

61是素数,因此ap-1当除以时p将得到1作为余数.

然而,如果p是非素数,通常的技巧是重复平方.

Answer 2

45^60 =
2025^30 = (33*61 + 12)^30 = 12^30 =
144^15 = (2*61 + 22)^15 = 22^15 =
10648^5 = ( 174*61 + 34)^5 = 34^5 =
45435424 = 744843 * 61 + 1 = 1

这里的平等意味着=(mod 61)