Krdytkyu

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

Calculate:

$$177^{20^{100500}} (mathrm{mod} 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}} (mathrm{mod} 60) &equiv (3cdot 59)^{20^{100500}} mathrm{mod} 60\
&equiv (3 mathrm{mod} 60)^{20^{100500}} cdot (59 mathrm{mod} 60)^{20^{100500}}\
&equiv (3 mathrm{mod} 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}} (mathrm{mod} 60)equiv 3 (mathrm{mod} 60)^{20^{100500}}$$

But I have no idea what to do here.

Thanks for your help.

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 $kge 1$. (For even numbers you might need $kge 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 81equiv 21 bmod 60
$$

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

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$

The answer is $21$. Proof follows:

First thing to notice is that the sequence
$$
a_n=177^nmod{60}
$$
is periodic with period $4$. It starts off like: ${57, 9, 33, 21, 57, 9, 33, 21,...}$. One can show this by induction. Therefore if $n$ is a multiple of $4$, $a_n=21$. The exponent $20^m$ is a multiple of $4$ for all positive integers $m$ which completes the proof.