Evaluate congruences with non-prime divisor with Fermat's Little Theorem I can evaluate $ 17^{2012}\bmod13$ with Fermat's little theorem because $13$ is a prime number. (Fermat's Little theorem says $a^{p-1}\bmod p\equiv1$.)
But what if when I need to evaluate for example $12^{1729}\bmod 36$? in this case, $36$ is not a prime.

Your example is slightly trivial, because already $12^2\equiv0\bmod36$. If the base and modulus were coprime, you could use Euler's theorem. In cases in between, where the base contains some but not all factors of the modulus, you can reduce by the common factors and then apply Euler's theorem.
