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

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.

• Hint: $3^1\equiv 3^5\pmod{60}$ Mar 22, 2017 at 21:50
• @rtybase he already figured that out Mar 22, 2017 at 21:51
• You can use \pmod as in $61\equiv1\pmod{60}$ and \bmod as in $61\bmod60=1$ $61\bmod60=1$. I was not sure whether the last occurrence is supposed to be $(3\bmod 60)^{exponent}$ rather than $3(\textrm{mod}60)^{exponent}$, so I did not edit that one. Mar 20, 2019 at 6:34

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

• This is indeed pretty neat (:. I will have a closer look at this function. And I have a question: what would happen if instead of $3^{20^{100500}}$ we'd have had $3^{21^{100500}}$. It seems to me that the exponent is not a multiple of $4$. I think we could write $21^{100500} = qp + 4$ for some suitable positive integers $p$ and $q$, but then how do we go about reducing the expression any further?
– asd
Mar 22, 2017 at 23:01
• $21^x\equiv 1^x \equiv 1\bmod 4$, so that would be even easier. Mar 22, 2017 at 23:02

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$

• I'd actually give this advice more generally: it is never a good idea to apply Euler's theorem except modulo prime powers (where you have no choice). Otherwise, it's much easier to factor $n$ into prime powers and do the computation for each of them, then reassemble the result using the Chinese remainder theorem. In many examples, such as this one, you never even end up doing any nontrivial multiplication. Mar 22, 2017 at 21:55
• A slight shortcut would be to determine the power modulo $20$. To do this, you can reduce the exponent modulo $\phi(20)=8$. Obviously this gives $0$, so the power is congruent to $1$ modulo $20$. Since it is divisble by $3$, you again get $21$ modulo $60$ Mar 22, 2017 at 22:54

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

• Did you compute $3^5$ by hand in order to know that $3^5=3\pmod{60}$ or there is another way to figure that out?
– asd
Mar 22, 2017 at 21:57
• @Jazz $3^5=243$ is pretty well known, and clearly $240$ is a multiple of $60$. Mar 22, 2017 at 22:09

The answer is $$21$$. Proof follows:

First thing to notice is that the sequence $$a_n=177^n\mod{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.

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.

1. 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