Hello,

use Euler's generalization of Fermat's Little Theorem : if and only if , , where is the Euler totient of .

In your case, is a prime number (lucky you), so . And . Therefore, . Good.

Now note that . Plug in the result you found with Euler's generalization, you find that :

.

still is a big number, so we are going to break it into pieces. You can thus write the following :

.

You can easily compute , so :

is not too big and can be computed quickly (if not, break it into two pieces), so . While we're at it, . We get :

.

And we are done ! We can now write :

.

(that is, )

--------

Can you see how I have repeatedly broken the original, gigantic number, into lots of smaller numbers, using Fermat's Generalized Little Theorem as a starting block and using algebra of indices to finish off the work ?