Can't use Euler's Theorem? I want to use Euler's theorem to calculate the following:
$14^{(2019^{2019})} \mod 60$
$a^{\phi(n)} \equiv 1 \mod n \iff \gcd(a,n) = 1$
Now I start with the outer one first:
$14^{(2019)}\mod 60 \iff \gcd(14,60) = 2$
Now I don't know how can I solve it ...
Can anyone suggest me any hints/further calculations?
Thank you in advance,
Kind Regards.
 A: You can't use Euler's theorem because $\gcd(14,60) > 1$.
But you can use the Chinese remainder theorem, using $60 = 4 \cdot 15$:
$$
\begin{align}
14^{(2019^{2019})} & \equiv  \hphantom{-} 0 \bmod 4
\\
14^{(2019^{2019})} & \equiv  -1 \bmod 15
\end{align}
$$
because
$$
\begin{align}
14^2 & \equiv  \hphantom{-} 0 \bmod 4
\\
14\hphantom{^2} & \equiv  -1 \bmod 15
\end{align}
$$
A: You can calculate separately $2^{2019^{2019}}$ and  $7^{2019^{2019}}$ first:


*

*It is not long to check that, if $n\ge 2$,
$$2^n\equiv\begin{cases}
16&\text{ if }n\equiv 0\mod 4,\\
32&\text{ if }n\equiv 1\mod 4,\\
4&\text{ if }n\equiv 2\mod 4,\\
8&\text{ if }n\equiv 3\mod 4.
\end{cases}$$
So we have to compute the exponent mod. $4$:
$$2019^{2019}\equiv (-1)^{2019}=-1\equiv3\mod 4\quad\text{and thus }\quad 2^{2019^{2019}}\equiv8\mod 60.$$

*As it is coprime to $60$, $7$ has order dividing $\varphi(60)=16$. Actually, $\;7^2=49\equiv -11\mod 60$, so $\;7^4\equiv (-11)^2=121\equiv 1$: $7$ has order $4$, so that
$$7^{2019^{2019}}\equiv 7^{2019^{2019}\bmod4}\equiv 7^3\equiv-77\equiv -17\mod 60.$$
A: Like How to find last two digits of $2^{2016}$, 
Get the last two digits of $16^{100}$ and $17^{100}$
what are the last two digits of $2016^{2017}$?
last two digits of $14^{5532}$?,
As $(14^n,60)=2^2$ for $n\ge2$
and as  $14\equiv-1\pmod{15}\implies14^m\equiv(-1)^m$
$\implies F_{m+2}=14^{m+2}=14^2\cdot14^m\equiv14^2(-1)^m\pmod{15\cdot14^2}$
$F_{m+2}\equiv14^2(-1)^m\pmod{15\cdot4}$ as $15\cdot4$ divides $15\cdot14^2$
$F_{m+2}\equiv16(-1)^m\pmod{60}$
If $m$ is odd like here $2019^{2019}-2,$ $$F_{m+2}\equiv16(-1)\pmod{60}\equiv-16+60$$
A: Here's a way:


*

*Get rid of the gcd,

*then attempt by Euler's theorem, then reformulate mod 60


$$gcd(14,60)=2; gcd(14,15)=1; 14^{2019^{2019}}\equiv 14^{3^3}\equiv -1^3\equiv -1\bmod 15$$  which adding back a factor of 4 coincides with $44 \bmod 60$
A: $n\ge 2\,\Rightarrow\, 4\mid 14^n\Rightarrow\,14^n\bmod 60 = 4 (14^n/4 \bmod  15) = 4((-1)^n 4) = \left\{\begin{align} &16\ \ {\rm if}\ \ 2\mid n\\ &44\ \ {\rm if}\ \ 2\nmid n\end{align}\right. $ 
