2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Have you heard about Fermat's little theorem and Euler's theorem? $\endgroup$ – Arthur Apr 26 '17 at 13:25
  • $\begingroup$ @RajivKaipa no that isn't the answer. $\endgroup$ – user169772 Apr 26 '17 at 13:33
  • $\begingroup$ @Arthur yes i have , but how to solve using them?? any ideas?? $\endgroup$ – user169772 Apr 26 '17 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – mdave16 Apr 26 '17 at 14:16
  • 1
    $\begingroup$ Hmm, asked 2 days ago: math.stackexchange.com/questions/2249496/…, not exactly answered though $\endgroup$ – enedil Apr 26 '17 at 15:19
0
$\begingroup$

$x \uparrow \uparrow k \mod m = x^{x \uparrow \uparrow (k-1) \mod \phi(m)} \mod m$.

Which is $O(k)$ repeating process.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.