Solving a^(b^c) using fermats little theorem

Question

How do I go about finding the solution to the following equation:

$a^{(b^c)} \equiv x \;(\bmod\; n)$

(assume $n$ does not divide $a$ for the purposes of using fermats little theorem)

Assume a and b can be somewhat small values around 5 to 100 and c can take values 1,000 to 10,000. What is the general algorithm for solving for $x$ using pen and paper?

I find this question pretty confusing because of the 3 exponents. I can solve regular problems of the type $a^{b} \equiv x \;(\bmod\; n)$ but I must be missing something with this one.

Example problems:

$2^{(6^{2015})} \equiv x \;(\bmod\; 19)$ - find $x$

$2^{(6^{2015})} \equiv y \;(\bmod\; 23)$ - find $y$ - really need help with this one

Answer 1

$23$ is prime so $2^{22} \equiv 1 \mod 23$

So $2^{6^{2015}} \equiv 2^k \mod 23$ where $6^{2015} \equiv k \mod 22$ so we must solve $6^{2015}\equiv k \mod 22$.

Use Chinese remainder theorem. $22 = 2*11$

$6^{2015} \equiv 6^5 \mod 11$ so $6^5 = 36*36*6\equiv 3*3*6 \equiv 54 \equiv -1 \mod 11$ and $6^{2015} \equiv 0 \mod 2$.

So $6^{2015} \equiv 10 \mod 22$.

So $2^{6^{2015}} \equiv 2^{10} \equiv 1024\equiv 12 \mod 23$.

====

I'm not familiar with the Chinese Remainder theorem, does it mean that I can simply split it into two separate questions of the two factors 2 and 11, do I just add the results then? And also.. how do I get the first part where you switch to mod 22 to solve for k?

Okay, Details.

By FLT $2^{22} \equiv 1 \mod 23$

So if $6^{2015} = 22m + r$ then $2^{5^{2015}}\equiv 2^{22m + r} \equiv (2^{22})^m*2^k \equiv 1*2^k \equiv 2^r \mod 23$.

So we must solve $6^{2015} = 22m + r$ or in other words we must solve $6^{2015} \equiv r \mod 22$.

Question 1: What is $6^{2015} \equiv r \mod 22$.

Now we can't use FLT because $6$ and $22$ are not relatively prime.

But we can use the Chinese remainder theorem that says.

If $n,m$ are relatively prime and if $x \equiv a \mod n$ and $x \equiv b \mod m$ then there is a unique solution to $x \mod nm$.

So $22 = 2*11$ and $\gcd (2,11) = 1$.

So if $x \equiv 6^{2015}\equiv 0 \mod 2$

and $x \equiv 6^{2015} \equiv (6^{10})^{201}*6^5 \equiv 6^5\equiv 10 \mod 11$

Then there will be a unique solution $6^{2015}\equiv x \mod 22$.

Now $0 \equiv 10 \mod 2$ and $10 \equiv 10 \mod 11$. And $10 \equiv 10 \mod 22$. so $x \equiv 10 \mod 22$ is a solution to $x\equiv 0 \mod 10$ and $x\equiv 10 \mod 11$. And by the chinese remainder theorem it is a unique solution.

So $6^{2015}\equiv 10 \mod 22$.

So $6^{2015} = 22m + 10$.

So $2^{6^{2015}} = 2^{22m + 10} \equiv (2^{22})^{m}*2^{10} \equiv 2^{10}\equiv 1024\equiv 12 \mod 23$.

=====

Okay, without CRT. We still need to find $6^{2015} \mod 22$.

$6^2 = 36 \equiv 14\equiv -8\mod 22$

$6^3 \equiv -8*6 \equiv -48 = -4 \mod 22$.

$6^4 \equiv -24 \equiv -2 \mod 22$

$6^5 \equiv -12 \equiv 10 \mod 22$

$6^6 \equiv 60 \equiv -6 \mod 22$

So $6^{2015} \equiv 6^{6*335+5}\equiv (-6)^{335}*6^{5}$

$\equiv (-6)^{6* 55+ 5}*10$

$\equiv (-6)^{55}*(-10)*10$

$ \equiv (-6)^{6*9 + 1}*(-100)$

$\equiv (-6)^9*(600)$

$\equiv (-6)^{6+3}* 6$

$\equiv (-6)*(-6)^3*6$

$\equiv 6^5 \equiv 10 \mod 22$.