Find the remainder of 3^(3^2009) ondivision by 55.
Im confusing that 55 is not prime, so how can we use fermat's little thm...
If , then , where stands for Euler's totient function
It follows that
Now study the congruence of modulo 40 (to use Euler's theorem for )
But . Since , we have that :
Thus there is some integer k such that
Does it look clear to you ?
A slight variation, which makes the arithmetic simpler, is to use Moo's method to find and . The numbers are then smaller, and you should easily find that Fermat's theorem gives the answers and . Then combine these (either by using the Chinese remainder theorem or just by looking at it) to get .