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.

Hint $\rm\ n\ge2\:\Rightarrow\:ab^2\:|\:(ab)^2\:|\:(ab)^n$ so $\rm\:36\:|\:12^n\,$ via $\rm\:a,b = 4,3.$
