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 $\displaystyle \text{gcd}(a,n)=1$, then $\displaystyle a^{\varphi(n)}\equiv 1 (\bmod n)$, where $\displaystyle \varphi$ stands for Euler's totient function

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

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

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

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

But $\displaystyle 2009=16 \times 125+9$

So $\displaystyle 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 $\displaystyle 3^9=3\cdot (3^4)^2=3 \cdot 81^2$. Since $\displaystyle 81 \equiv 1 (\bmod 40)$, we have that :
$\displaystyle \boxed{3^{2009} \equiv 3^9 (\bmod 40) \equiv 3 (\bmod 40)}$

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

---> $\displaystyle 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 $\displaystyle 3^{3^{2009}}\!\!\!\!\!\pmod5$ and $\displaystyle 3^{3^{2009}}\!\!\!\!\!\pmod{11}$. The numbers are then smaller, and you should easily find that Fermat's theorem gives the answers $\displaystyle 2\!\!\!\pmod5$ and $\displaystyle 5\!\!\!\pmod{11}$. Then combine these (either by using the Chinese remainder theorem or just by looking at it) to get $\displaystyle 27\!\!\!\pmod{55}$.