<s>[INST] What is the remainder when dividing $11^{(345^{678})}$ by 13? So basically I figured out that this problem comes down to the following:
We want to find the answer to $11^{(345^{678})} \ \text{mod} \ 13$.
Then, because $11$ and $13$ are coprime, we know that $11^{\phi(13)} = 1 \  
 \text{mod} \ 13$. Because 13 is prime, we know that $\phi(13) = 12$. So 
$11^{12x} = 1 \ \text{mod} \  13 $ for any integer x. 
Then we need to find how many times 12 fits into $345^{678}$, so $345^{678} \ \text{mod} \ 12 $. However, $345$ and $12$ are not coprime, so we can't use Euler's theorem. This is the part where I don't actually know what to do anymore.
I tried the following: 345 mod 12 = 9 mod 12, so $345^{678} \ \text{mod} \ 12 = 9^{678} \ \text{mod} \ 12$.
We know that $9^2 \ \text{mod} \ 12 = 81 \ \text{mod} \ 12 = 9 \ \text{mod} \ 12$. And we know that $9^4 \ \text{mod} \ 12 = 9^2 \cdot 9^2 \ \text{mod} \ 12 = 9 \ \text{mod} \ 12$. So $9^2$, $9^4$, $9^8$, $9^{16}$, $9^{32}$, $9^{64}$,$9^{128}$, $9^{256}$ and $9^{512}$ are all 9 in mod 12.
So then, $9^{678} \ \text{mod} \ 12  = 9^{512} \cdot 9^{128} \cdot 9^{32} \cdot 9^{4} \cdot 9^2 \ \text{mod} \ 12  = 9^5 \ \text{mod} \ 12  = 9 \ \text{mod} \ 12 $.
Then, going back to the original question, we know that we need to calculate $11^{9} \ \text{mod} \ 13  = 11^8 \cdot 11 \ \text{mod} \ 13$.
Using the same trick as with the 9, I get that $11^{9} \ \text{mod} \ 13  = 8 \ \text{mod} \ 13$.
Is this correct? If not, what am I doing wrong? Is there a better way to attack such problems?
Thanks for reading,
K.
 [/INST] As $11\equiv-2\pmod{13},$
$11^{(345^{678})}\equiv(-2)^{(345^{678})}\pmod{13}$
Now $(-2)^6\equiv-1\pmod{13}\implies(-2)^{12}\equiv1,$
and $(-2)^{(345^{678})}\equiv(-2)^{(345^{678}\pmod{12})}\pmod{13}$
Now as $345\equiv0\pmod3\implies345^{678}\equiv0\  \ \ \ (1)$
and $345\equiv1\pmod4\implies345^{678}\equiv1\  \ \ \ (2)$
Using $(1),(2)$ by observation, $345^{678}\equiv9\pmod{12}$
$(-2)^{(345^{678}\pmod{12})}\equiv(-2)^9\pmod{13}\equiv?$
</s>