$3^{10^{100}} \pmod {13}$
It was originally $(10^{100})^{(10^{100})}$ (i.e. googol^googol), but I simplified it down to what I have there. However, I can't seem to reduce the exponent without changing the value of the entire expression.
I was thinking of making it $3^{10\cdot 10^{99}}$, but that doesn't seem to retain the original value of the expression, and even if it did, I don't think I can separate the two terms into $(3^{10})^{10^{99}}$...
Any pointers?
On
One approach is to use Euler’s theorem/Fermat’s little theorem. Since 3 is relatively prime to 13, $3^{12} \equiv 1 \pmod{13}$, and so you can reduce the exponent modulo 12 without changing the result. More explicitly, if $10^100=12a+b$, then $$3^{10^{100}}=3^{12a+b}=(3^{12})^{a}3^b\equiv 1^a 3^b\equiv 3^b \pmod{13}$$
However, this leaves the problem of reducing $10^{100} \pmod{12}$, and we can’t directly apply Euler's theorem because 10 is not relatively prime to 12. We can get around this by using the Chinese remainder theorem. Since $12=3\cdot 4$ is a factorization into prime powers, we can determine $10^{100}\pmod{12}$ from $10^{100}\pmod 3$ and $10^{100}\pmod 4$.
It turns out that the CRT converts this into a solvable problem without even invoking Euler's theorem a second time. We have $$10^{100}\equiv 2^{100}\equiv 4^{50}\equiv 0 \pmod 4,$$ and $$10^{100}\equiv 1^{100}\equiv 1\pmod 3.$$ Since $4\equiv 0 \pmod 4$ and $4\equiv 1 \pmod 3$, this tells us that $10^{100}\equiv 4 \pmod 12$.
Putting everything together, $$3^{10^{100}} \pmod{13}=3^{12k+4}\equiv 3^{4} \equiv 3 \pmod{13}$$
Note that $3^3 \equiv 1 \pmod{13}$, so you need only to reduce the exponent modulo $3$.
$$10^{100} \equiv 1^{100} \equiv 1 \pmod{3},$$
s0
$$3^{10^{100}} \equiv 3^1 \equiv 3 \pmod{13}.$$