Numbers crushing numbers

Let $N = 12^{14^{16}}$ . We need to find $N \bmod 42$ . Since $\gcd (12, 42) \ne 1$ , we have to consider that factors 6 and 7 of 42 separately using Chinese remainder theorem .

Factor 6: $N \equiv 0 \text{ (mod 6)}$ .

Factor 7: Since $\gcd(12,7) = 1$ , we can apply Euler's theorem and the Euler's totient function $\phi(7) = 6$ . Then $N \equiv 12^{14^{16} \bmod \phi(7)} \equiv 12^{14^{16} \bmod 6} \text{ (mod 7)}$ . Again, $\gcd (14, 6) \ne 1$ , then we consider $14^{16} \equiv 0 \text{ (mod 2)}$ and $14^{16 \bmod \phi(3)} \equiv 14^{16 \bmod 2} \equiv 14^0 \equiv 1 \text{ (mod 3)}$ . Implying that $14^{16} \equiv 3n+1$ , where $n$ is an integer and $3n+1 \equiv 0 \text{ (mod 2)}$ $\implies n = 1$ , $\implies 14^{16} \bmod 6 =3(1)+1= 4$ . Then $N \equiv 12^4 \equiv (14-2)^4 \equiv 2^4 \equiv 16 \equiv 2 \text{ (mod 7)}$ .

Now, we have: $N \equiv 7m + 2$ , where $m$ is an integer, and $7m + 2 \equiv 0 \text{ (mod 6)}$ $\implies m = 4$ and $N \equiv 7(4)+2 \equiv \boxed{30} \text{ (mod 42)}$