How to calculate $14^{2017^{2017}} \mod 60$?

Question

$14^{2017^{2017}} \mod 60$

So, I know that I should begin with decomposing $60$ to the prime factors, which are: $ 3, 2^2, 5$, now I should calculate $14^{2017^{2017}} mod$ all three of these prime factors.

My question is, what is the easiest way of calculating $14^{2017^{2017}} \mod 3$?

Answer 1

Sketch:

Since $14\equiv 2\pmod 3$,

$$14^{2017^{2017}}\equiv 2^{2017^{2017}}\pmod 3.$$

Now, we know that the powers of $2$ satisfy \begin{align*} 2^1=2&\equiv 2\pmod 3\\ 2^2=4&\equiv 1\pmod 3\\ 2^3=8&\equiv 2\pmod 3\\ 2^4=16&\equiv 1\pmod 3\\ 2^5=32&\equiv 2\pmod 3 \end{align*} and so on.

In other words, since $2^2\equiv 1\pmod 3$, we only need to compute the power modulo $2$. Since $2017^{2017}\equiv 1^{2017}\equiv 1\pmod 2$, we know that the power on $2$ is odd. Hence $$ 14^{2017^{2017}}\equiv 2^{2017^{2017}}\equiv 2^1\equiv 2\pmod 3. $$

Answer 2

In fact you don't need to do the primes separately. $$\phi(60)=16$$ And $$2017\equiv 1\mod 16$$

So $$7^{2017^{2017}}\equiv 7\mod 60$$

Moreover $$2^{2017^{2017}}\equiv 2\mod 15$$ and $$2^{2017^{2017}}\equiv 0\mod 4$$ thus we have

$$ 2^{2017^{2017}}\equiv 32\mod 60$$ and

$$14^{2017^{2017}}\equiv 7\cdot 32\equiv 44\mod 60$$

Answer 3

By Euler's Theorem, $14^{\phi(60)}\equiv 1\mod 60$. We can calculate, using the product formula for the $\phi$ function, that $\phi(60)=16$. So we need to find $2017^{2017}\mod 16$. Now we repeat: $2017\equiv 1\mod 16$, so $$2017^{2017}\equiv 1^{2017}\equiv 1\mod 16$$ Then we have $$14^{2017^{2017}}\equiv 14^{k(16)+1}\equiv 1\cdot 14\equiv 14\mod 60$$

Edit: As noted by multiple people in the comments, we cannot use Euler's Theorem because $14$ and $60$ are not coprime. One resolution is factor $14=2\cdot 7$, and then apply Euler's Theorem to the second factor. As before, $2017\equiv 1\mod 16$ and we get

$$14^{2017^{2017}}=2^{2017^{2017}}7^{2017^{2017}}\equiv 2^{2017^{2017}}\cdot 7 \mod 60$$

Now we have to find $2^{2017^{2017}}\mod 60$. Note that $2^2\equiv 4\mod 60$ and $2^6=64\equiv 4\mod 60$. So computing $2^k\mod 60$ just amounts to computing the residue of $k \mod 4$ for $k\geq 2$. Well, working modulo $4$, $$2017^{2017}\equiv 1^{2017}\equiv 1\mod 4$$ Using this to find $2^{2017^{2017}}\mod 60$, we have $$2^{2017^{2017}}\equiv 2^5\equiv 32\mod 60$$ (Remember we need $k$ at least $2$ to use the remainder mod 4 in the exponent). Putting it all together, we have $$14^{2017^{2017}}\equiv 32\cdot 7\equiv 44\mod 60$$

Answer 4

Notice that $14$ to any power greater than one is divisible by $4.$ so this number is divisible by $4.$ On the other hand, $14 \equiv -1 \mod 15,$ and since $2017^{2017}$ is odd, the number is equal to $-1 \mod 15.$ So, the number is equal to $44 \mod 60.$

Answer 5

Decompose $14^{2017^{2017}}=2^{2017^{2017}}7^{2017^{2017}} $.

Now, by Euler's theorem, as $7$ is coprime to $60$, $\,7^{\varphi(60)}=7^{16}\equiv 1\mod60$, so $$7^{2017^{2017}}\equiv7^{2017^{2017}\bmod 16}\equiv7^{1^{2017}\bmod 16}\equiv7\mod60.$$ On the other hand, the successive powers of $2\bmod60$ follow a cycle of length $4$ for $n\ge 2$: $$\begin{array}{c|ccccc} n&1&\color{blue}2&3&4&5&\color{blue}6&\dots\\ 2^n&2&\color{red}4&8&16&32&\color{red}4&\dots \end{array}$$ so that we have to find the value of $\bmod4$. This is easy: $2017\equiv 1\mod4$, so $$2^{2017^{2017}}\equiv 2^{1^{2017}}\equiv2^5\equiv32\mod 60$$ (don't forget the cycle begins at $n=2$).

Summing up these results, we obtain $$14^{2017^{2017}}\equiv 32\cdot 7=224\equiv 44\mod60.$$