Hello !

Your result is nearly correct. You must simplify the exponent too, in order to be able to compute it efficiently (although this can be considered as a tractable exponent in most cases), and to perform the modulus operation to obtain your remainder in the ring .

Here is a method to achieve this using Fermat's Little Theorem (with the Euler generalization).

It states that for any . Note that is prime, thus .

Therefore, you know that . Note that you can equally take a multiple of as exponent without changing the congruence, thus you can extend this even further : ,[1].

Let's attack our problem now : consider the base as a whole, namely , we will work with it later. The exponent is . Thus you have :

And you want to solve this for . Note that a little bit of algebra can be done here, to be able to use[1]on this problem.

Thus :

Since is a multiple of , we can apply[1], and we get :

Or, more simply :

Now that we've simplified the astronomical exponent, let's work out (this is what you have successfully done). Recall that :

Easily enough, , , .

Thus :

Finally, we are left with :

And this is easily solved :

Conclusion: .

Please mention it if you do not understand any of these steps.