# 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.

-
What if it's $17^1729$ ? – xiamx Oct 21 '12 at 19:17
@xiamx: I presume you meant $17^{1729}$. (You need to enclose the exponent in braces to group it, since only the first object after the circumflex is interpreted as the exponent.) In that case, since $17$ and $36$ are coprime, as stated in the answer you can apply Euler's theorem. – joriki Oct 21 '12 at 19:21

This one's easy:

$$12^1=12=12\pmod{36}\;\;,\;\;12^2=144=0\pmod{36}\,...\,12^n=0\pmod{36}\,\,,\,n\geq 2$$

-

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

-