Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
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$$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.