find the remainder

**luoginator** · March 21st 2009, 11:43 PM

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!

**Moo** · March 22nd 2009, 12:04 AM

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 ?

**Opalg** · March 22nd 2009, 10:19 AM

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}$ .

Thread: find the remainder

LinkBack

Thread Tools

Display

find the remainder

Similar Math Help Forum Discussions

Find the remainder

find the remainder

Find the remainder?

find remainder

Please help to find k and remainder

Search Tags