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.

This one's easy:
$$12^1=12=12\pmod{36}\;\;,\;\;12^2=144=0\pmod{36}\,...\,12^n=0\pmod{36}\,\,,\,n\geq 2$$
