1. find the remainder

Find the remainder of 3^(3^2009) on
division by 55.

Im confusing that 55 is not prime, so how can we use fermat's little thm...

Cheers!

2. Hello,
Originally Posted by luoginator
Find the remainder of 3^(3^2009) on
division by 55.

Im confusing that 55 is not prime, so how can we use fermat's little thm...

Cheers!
Euler's theorem is stronger :
If $\text{gcd}(a,n)=1$, then $a^{\varphi(n)}\equiv 1 (\bmod n)$, where $\varphi$ stands for Euler's totient function

$55=5 \cdot 11 \Rightarrow \varphi(55)=4 \cdot 10=40$
It follows that $3^{40} \equiv 1 (\bmod 55)$

Now study the congruence of $3^{2009}$ modulo 40 (to use Euler's theorem for $3^{3^{2009}}$)

$40=2^3 \cdot 5 \Rightarrow \varphi(40)=(2^3-2^2) \cdot 4=16$

Hence $3^{16} \equiv 1 (\bmod 40)$

But $2009=16 \times 125+9$

So $3^{2009}=3^{16 \times 125+9}=(3^{16})^{125} \cdot 3^9 \equiv 1^{125} \cdot 3^9 (\bmod 40) \equiv 3^9 (\bmod 40)$
But $3^9=3\cdot (3^4)^2=3 \cdot 81^2$. Since $81 \equiv 1 (\bmod 40)$, we have that :
$\boxed{3^{2009} \equiv 3^9 (\bmod 40) \equiv 3 (\bmod 40)}$

Thus there is some integer k such that $3^{2009}=3+40k$

---> $3^{3^{2009}}=3^{3+40k}=3^3 \cdot (3^{40})^k \equiv 3^3 \cdot 1^k (\bmod 55) \equiv 27 (\bmod 55)$

Does it look clear to you ?

3. A slight variation, which makes the arithmetic simpler, is to use Moo's method to find $3^{3^{2009}}\!\!\!\!\!\pmod5$ and $3^{3^{2009}}\!\!\!\!\!\pmod{11}$. The numbers are then smaller, and you should easily find that Fermat's theorem gives the answers $2\!\!\!\pmod5$ and $5\!\!\!\pmod{11}$. Then combine these (either by using the Chinese remainder theorem or just by looking at it) to get $27\!\!\!\pmod{55}$.