Power tower modulus I'm doing a programming challenge and I can't wrap my head around of finding an Euler totient when the modulus and the base aren't co-primes.
So I have: 
$$4 ^ {4 ^ 4}(mod\;10)$$
I understand that 4 and 10 aren't co-primes. So I've tried to use mod distributive law and then find a totient, but it doesn't work. In a task it is said that it's possible somehow to modify the totient function that it will work with non-coprimes.
I know how totient function works, I know properties of it and how to find a totient, but only with co-primes.
P.S. I'm making an algorithm so shortcuts like $(-1)^n$ etc won't work.
 A: I solved the problem by using Chinese reminder theorem for prime values of $(mod\;10)$, i.e. $(mod\;(2*5))$
\begin{cases}
x = 4^{4^4}(mod\;2)\\
x = 4^{4^4}(mod\;5)\\
\end{cases}
\begin{cases}
x = 4^{4^4}(mod\;2)=0\\
x= 4^{4^4}(mod\;5) = 4^{4(mod\;\phi(5))}(mod\;5) = 4^0(mod\;5) = 1(mod\;5)\\
\end{cases}
where $\phi(n)$ is Euler's totient function. Although I could use the simplification $4^2 = 1(mod\;5)$as mentioned in the comments, but for an algorithm it's easier to find a totient.
Next step is to put the values into the Chinese reminder formula $$x = 0* \frac{10}{2}*(\frac{10}{2})^{-1}(mod\;2) + 1* \frac{10}{5}*(\frac{10}{5})^{-1}(mod\;5) $$ which equals to
$$x = 0 + 1 * 2*2^{-1}(mod\;5) $$
$$2^{-1}(mod\;5) = 2^{\phi(5) - 1}(mod\;5) = 2^3(mod\;5) = 3(mod\;5)$$
So the result is
$$x = 0 + 2 * 3 = 6(mod\;10)$$
Thanks everyone.
More resources for future reference:
Specific steps in applying the Chinese Remainder Theorem to solve modular problem splitting modulus
https://en.wikipedia.org/wiki/Modular_arithmetic
