Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

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|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|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|improve this answer

Your Answer

 
discard

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.