Calculate: $177^{20^{100500}}\pmod{60}$

Question

I'm taking my first steps into modular arithmetic and I'm already stuck.

Calculate:

$$177^{20^{100500}}\pmod{60}$$

I don't know how to tackle this one. So far I've been applying Euler's Theorem and Fermat Little Theorem to compute more simple expressions, but here we notice that $\mathrm{gdc}(177,60) = 3 \neq 1$ so, to my understanding, I can't apply any of the two theorems. I tried the following instead:

\begin{align} 177^{20^{100500}} \pmod{60} &\equiv (3\cdot 59)^{20^{100500}}\bmod 60\\ &\equiv (3 \bmod 60)^{20^{100500}} \cdot (59\bmod60)^{20^{100500}}\\ &\equiv (3 \bmod 60)^{20^{100500}} \cdot (-1)^{20^{100500}} \end{align}

Since $20^{n}$ is even $\forall n \in \mathbb{N}$ then $(-1)^{20^{100500}} = 1$. Therefore

$$177^{20^{100500}} \pmod{60}\equiv 3\ (\mathrm{mod}\ 60)^{20^{100500}}$$

But I have no idea what to do here.

Thanks for your help.

Answer 1

You got off to a good start there.

You know about Euler's Theroem, and Euler's totient, so I can add another tool to the box with the Carmichael function $\lambda$ which will give you the largest exponential cycle length (and still a value that all shorter cycles will divide). This combines prime power values through least common multiple rather than simple multiplication as for Euler's totient.

Here $\lambda(60) ={\rm lcm}(\lambda(2^2),\lambda(3),\lambda(5)) ={\rm lcm}(2,2,4) =4$. So for any odd number $a$, since there are no higher odd prime powers in $60$, you will have $a^{k+4}\equiv a^k \bmod 60$ for $k\ge 1$. (For even numbers you might need $k\ge 2$, since $2^2 \mid 60$). So $20^{100500}$ is just a huge multiple of $4$, and we can cast out all those $4$s all the way down to $3^4$. So the final result is

$$177^{20^{100500}} \equiv \underset {(\text{your result})}{3^{20^{100500}}}\equiv \underset {(\lambda(60)=4)}{3^4}\equiv 81\equiv 21 \bmod 60 $$

Answer 2

The easiest way to handle such extremely powers is to calculate the power modulo $3$, $4$ and $5$ and apply the chinese remainder theorem. These modulo calculations are not very difficult :

Modulo $3$ is trivial; $177$ is divisble by $3$, so the residue is $0$.

Modulo $4$ is trivial as well ; $177$ has residue $1$ modulo $4$, so the power has residue $1$ modulo $4$ as well.

For Modulo $5$, you can reduce the exponent modulo $4$, which gives $0$, so the residue modulo $5$ is $2^0=1$.

So, the power is congruent $0$ modulo $3$ , $1$ modulo $4$ and $1$ modulo $5$. That gives $21$ modulo $60$

Answer 3

$3^5=3\pmod{60}$ so take the exponent modulo $4$ and then check to see if you need to multiply by $-1$.

Answer 4

Is this a mathematically sound approach, or just brute-force sheer luck ?

-- it tackles exponent reduction in an unconventional way of directly dealing with the 3rd layer first while paying close to zero attention to the 20 in the middle layer, or the prime factors of the modulus :

---

1. 100500 % 60, chop off 1 trailing zero each => 10050 % 6

---

Any power of 10, mod % 6, is always 4, but since the digits add to 6 anyway in this case, the 4 isn't even needed.

This alone took the entire top layer to a zeroth-power, which is base-agnostic. The base could be something funky like ♕^0, ♠^0, or even ♬^0, and you'll still get back a 1.

---

2. So now the problem is reduced to ≡ (-3) ^ 20 ^ 1 % 60, or ≡ 9 ^ 10 % 60.

---

All powers of 9, mod % 60, has a boring 2-period cyclicality, so it came down to whether the current exponent is odd or even. If it's odd, the result is 9, otherwise, it's 21.

10 is obviously even, so the result should be congruent to

---

 ≡ 9^2 % 60 
 ≡  81 % 60 
 =  81 - 60 
 ----------
 =       21

---