How to find the following number using modular arithmetic

Question

Suppose I have a number $x$ such that, $$ x \equiv 31^{29} \text{ (mod 57)} $$ How can I find $x$ using properties of modular arithmetic. Will it involve a special theorem?

Answer 1

Here is one solution. By the Chinese Remainder Theorem, one reduces to solving the same equation mod 3 and mod 19, as we can patch those together at the end.

Mod 3: the easy case $$31^{29} = 1^{29} = 1$$

Mod 19: just a long chain of combining small groups of multiplications and reducing mod 19 as frequently as possible to keep the arithmetic easy $$31^{29} = 31^{11} = 12^{11} = 12*(12)^{2*5} = 12*(144)^5 = 12*(11)^5= 12*11*(11)^4$$ $$=12*11*(121)^2 = 12*11*7^2 = 12*11*49 = 12*11*11 = 12*7 = 84 = 8$$

So altogether the solution is congruent to 1 mod 3 and 8 mod 19, which we see lifts to 46 mod 57 (as usual for the CRT, just start with one solution, 8 mod 19, and add multiples of 19 until it is congruent to 1 mod 3).

Sometimes there are tricks to speed things up but these numbers look sort of "random" to me.