Results 1 to 3 of 3

Thread: find the remainder

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    14

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by luoginator View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    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}$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the remainder
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 22nd 2009, 04:47 PM
  2. find the remainder
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 5th 2009, 07:43 PM
  3. Find the remainder?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 2nd 2009, 10:19 PM
  4. find remainder
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 2nd 2007, 07:02 PM
  5. Please help to find k and remainder
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Oct 15th 2007, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum