0
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I got 3 as the answer - is that correct? $\endgroup$ – user1023 Sep 22 '16 at 23:45
  • $\begingroup$ @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}$ $\endgroup$ – Stefan4024 Sep 22 '16 at 23:47
  • $\begingroup$ So for the 2nd one, we get $13^{13} \equiv 1 (mod 8)$, right? $\endgroup$ – user1023 Sep 23 '16 at 0:00
  • $\begingroup$ @user1023 I'm afraid not. Note that $13^4 \equiv 1 \pmod 8$, then $13^{13} \equiv 13 \equiv 5 \pmod 8$ $\endgroup$ – Stefan4024 Sep 23 '16 at 0:03
  • 1
    $\begingroup$ So the answer for 2nd part is 13, right? $\endgroup$ – user1023 Sep 23 '16 at 0:19

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.