# Use Fermat's little theorem to find remainder of powers

I have to use Fermat's little theorem to find the value of$$x \uparrow \uparrow k \mod m = \underbrace{x^{x^{{}^{{{.\,}^{.\,^{.\,^{x}}}}}}}}_{k\text{ times}} \mod m,$$ where $x$ is repeated in power $k-1$ times and $m$ is any number.

That is, if $x=5$, $k=3$ and $m=3$, then I need to find $\ 5^{5^5} \mod 3$ .

Also note that $x$ is always a prime number.

It has been in my mind for quite a while now I can't find an answer.

• Have you heard about Fermat's little theorem and Euler's theorem? – Arthur Apr 26 '17 at 13:25
• @RajivKaipa no that isn't the answer. – user169772 Apr 26 '17 at 13:33
• @Arthur yes i have , but how to solve using them?? any ideas?? – user169772 Apr 26 '17 at 13:34
• Everything hinges on the fact that $a^{\phi(m)} \equiv 1 \mod m$. So if I do the more complicated example of $5\uparrow\uparrow 4 \mod 6$, we should see all the machinery required. Because $5^{\phi(6)} \equiv 1$, we should consider $5\uparrow\uparrow 3 \mod \phi(6) = 2$, but this is trivial since $5 \equiv 1 \mod 2$. So $5\uparrow\uparrow 4 \equiv 5^1 \mod 6$. So the remainder is 5. This is quite simple, but if you wouldn't mind waiting a week, I'll have more time then and can write a really nice answer. – mdave16 Apr 26 '17 at 14:16
• Hmm, asked 2 days ago: math.stackexchange.com/questions/2249496/…, not exactly answered though – enedil Apr 26 '17 at 15:19

$x \uparrow \uparrow k \mod m = x^{x \uparrow \uparrow (k-1) \mod \phi(m)} \mod m$.
Which is $O(k)$ repeating process.