# Remainder of a power tower under modulo $2013$

I have an expression like this:

$$\left(\large 6000^{5999^{5998^{5997^{{\ldots^{1}}}}}}\right)\bmod 2013$$

Then which method should I use to solve it? Please provide the method not the answer.

Editor's Note: Note that this is a power tower with different values and not the same value as with general tetration. Also, don't confuse tetration with exponentiation. Both are completely different.

• In which order should the exponentiations be taken? My guess is 6000^(5999^(5998^5997 etc ))) but (((6000^5999)^5998)^5997 etc) seems somewhat plausible as well. – Rolf Hoyer Apr 4 '15 at 7:40
• Is there a minus sign before 6000? – user228113 Apr 4 '15 at 7:40
• @PrasunBiswas No, $(2013,6000)=3\neq 1$, so you can't just directly use Euler's theorem. – user26486 Apr 4 '15 at 13:36
• @user31415, Yes, I noticed that now. I'm removing my comment. :) – Prasun Biswas Apr 4 '15 at 13:42
• @PrasunBiswas hey! – Confuse Jul 18 '15 at 6:52

Hint: Work out the answer modulo $3$, $11$ and $61$ (the prime factors of $2013$) separately. Use Euler's theorem to climb the exponent ladder. In the end combine the answers by using the Chinese remainder theorem.