121 = 11^2
Phi(121) = 11*10 = 110
1000 Mod 110 = 1000 - 990 = 10
2^1000 Mod 121 = 2^10 Mod 121
In the following everything is Mod 121:
2^7 = 128 = 7
2^10 = 7 * 2^3 = 56
Compute 2^1000(mod 121) using Euler.
1 answer