10楼
@多项式之父 让我用欧拉定理算2^(3^(...^(99^100))..) mod 123457的余数.
咱就是说, 这种简单问题还是别问了.
φ(123457) = 123456
φ(123456) = 41088
φ(41088) = 13568
φ(13568) = 6656
φ(6656) = 3072
φ(3072) = 1024
以此类推, 后面是512, 256, 128, 64, 32, 16, 8, 4, 2, 1
记f(k) = k^(k+1)^...^100
则f(18) mod 1 = 0, f(17) mod 2 = 17^0 = 1, f(16) mod 4 = 16^1 mod 4 = 0, 然后依次下去得到 (简写)
f( 16 ) -> 0
f( 15 ) -> 1
f( 14 ) -> 14
f( 13 ) -> 25
f( 12 ) -> 0
f( 11 ) -> 1
f( 10 ) -> 10
f( 9 ) -> 401
f( 8 ) -> 0
f( 7 ) -> 1
f( 6 ) -> 6
f( 5 ) -> 2057
f( 4 ) -> 4864
f( 3 ) -> 36033
所以f(2) mod 123457 = 2^36033 mod 123457 = 113778
有可能算错了, 也不排除有更聪明的办法. 但这是一个完全可行的做法.