0

$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?

Ernie060
  • 6,073
bobbyjeo2
  • 110

2 Answers2

3

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}.$$

B. Goddard
  • 1
  • why can you just reduce the exponent mod 3? In other words, where did that formula come from? – bobbyjeo2 Nov 03 '18 at 20:31
  • Every group of three $3$'s is $1$ modulo 13. So you just need to know how many groups of three you can make out of a googal $3$'s They all multiply out to $1$. Then there are either zero, one or two $3$'s left over. – B. Goddard Nov 03 '18 at 20:35
1

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}$$

Aaron
  • 24,207
  • I am still considerably confused about these two theorems, as I learned them less than 2 days prior to this comment, so this answer makes little sense to me... I will definitely keep this response in mind though, as it will probably help me understand these theorems. – bobbyjeo2 Nov 03 '18 at 20:34
  • Then this is the perfect opportunity to get more comfortable with them by working through the solution to appreciate how they are used. – Aaron Nov 03 '18 at 20:37
  • @bobbyjeo2 I have updated my answer so that things should be clearer for you. – Aaron Nov 03 '18 at 21:56