# Double exponent Euler- FLT

I am asked to determine $13^{13^{13}} \bmod 10$ and $13^{13^{13}} \bmod 15$

I know I have to use the Fermat's Little Theorem and Euler and find a $k$ s.t. $13^k\equiv 1 \pmod{10}$. By trial and error I found $k=4$. However, I don't quite understand what's happening here. Can someone explain this to me?

• – Henry Sep 22 '16 at 23:23

## 1 Answer

Actually you can find that $k$ is a divisor of $4$ by Euler's Formula. Anyway now we want to find the residue of $13^{13}$ modulo $4$. Assume it's $n$ and $13^{13} = 4m + n$. Then we have that:

$$13^{13^{13}} \equiv 13^{4m + n} \equiv (13^4)^m \cdot 13^n \equiv 1^m \equiv 13^n \pmod{10}$$

Therefore we have effectivelly reduced the problem to computing the residue of a much smaller number.

Now you should be able to finish this on you own, as well as solve the second question.

• I got 3 as the answer - is that correct? – user1023 Sep 22 '16 at 23:45
• @user1023 Yes, as $13^{13} \equiv 1 \pmod 4 \implies n=1$, which means that $13^{13^{13}} \equiv 13^1 \equiv 3 \pmod {10}$ – Stefan4024 Sep 22 '16 at 23:47
• So for the 2nd one, we get $13^{13} \equiv 1 (mod 8)$, right? – user1023 Sep 23 '16 at 0:00
• @user1023 I'm afraid not. Note that $13^4 \equiv 1 \pmod 8$, then $13^{13} \equiv 13 \equiv 5 \pmod 8$ – Stefan4024 Sep 23 '16 at 0:03
• So the answer for 2nd part is 13, right? – user1023 Sep 23 '16 at 0:19