Power tower modulus

Question

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.

Answer 1

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