求高手如何解(5^13)mod77?我知道答案等于26 听别人说可以用类似费马小定理的公式 ps 请给我一些可用的公式
2019-06-26
求高手如何解(5^13)mod77?
我知道答案等于26 听别人说可以用类似费马小定理的公式
ps 请给我一些可用的公式
优质解答
(a^b) mod c=[(a mod c)^b] mod c(a*b) mod c=[(a mod c)*b] mod c
（5^13)mod77=[(5^12)mod77*5]mod77其中(5^12)mod77={[(5^3)mod77]^4}mod77其中(5^3)mod77=48
所以(5^12)mod77=(48^4)mod77={[(48^2)mod77]^2}mod77
其中(48^2)mod77=71
所以(5^12)mod77=(71^2)mod77=36
所以(5^13)mod77=(36*5)mod77=26
(a^b) mod c=[(a mod c)^b] mod c(a*b) mod c=[(a mod c)*b] mod c
（5^13)mod77=[(5^12)mod77*5]mod77其中(5^12)mod77={[(5^3)mod77]^4}mod77其中(5^3)mod77=48
所以(5^12)mod77=(48^4)mod77={[(48^2)mod77]^2}mod77
其中(48^2)mod77=71
所以(5^12)mod77=(71^2)mod77=36
所以(5^13)mod77=(36*5)mod77=26