Results 1 to 3 of 3

Math Help - 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 \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 ?
    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
    7
    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}.
    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: November 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: December 2nd 2007, 07:02 PM
  5. Please help to find k and remainder
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 15th 2007, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum