Results 1 to 7 of 7

Math Help - Very tricky and interesting modular question

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Very tricky and interesting modular question

    This is a very tricky question:
    Find the last three digits of
    2008^2007^2006^2005^...^1

    If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

    Good luck, I know the answer, and will tell you if you get it!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Exclamation

    Quote Originally Posted by elemental View Post
    This is a very tricky question:
    Find the last three digits of
    2008^2007^2006^2005^...^1

    If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

    Good luck, I know the answer, and will tell you if you get it!
    James Bond +1 ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elemental View Post
    This is a very tricky question:
    Find the last three digits of
    2008^2007^2006^2005^...^1

    If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

    Good luck, I know the answer, and will tell you if you get it!
    Spoiler:

    Preamble: I think there's a more elegant way to write down the same type of reasoning, but this is the first that came to mind.

    Combination of Euler's theorem and Chinese remainder theorem.

    2008^{2007^{2006^{\dots^{1}}}} \equiv 8^{2007^{2006^{\dots^{1}}}} \equiv x\ (\text{mod}\ 1000)

    Solve

    8^{2007^{2006^{\dots^{1}}}} \equiv a\ (\text{mod}\ 2^3)

    8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)

    and then combine with CRT.

    Note that 8^{2007^{2006^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)

    Solve 8^{2007^{2006^{\dots^{1}}}} \equiv b\ (\text{mod}\ 5^3)

    \gcd(8,5^3) = 1

    Use Euler's theorem

    \varphi(5^3)=100

    Reduce to finding 2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{2006^{2005^{\dots^{1}}}} \equiv c\ (\text{mod}\ 100)

    \gcd(7,100) = 1

    Use Euler's theorem

    \varphi(100)=40=2^3\cdot5

    2006^{2005^{2004^{\dots^{1}}}} \equiv 6^{2005^{2004^{\dots^{1}}}} \equiv d\ (\text{mod}\ 40)

    \gcd(6,40) = 2

    Solve

    6^{2005^{2004^{\dots^{1}}}} \equiv e\ (\text{mod}\ 2^3)

    6^{2005^{2004^{\dots^{1}}}} \equiv f\ (\text{mod}\ 5)

    Note that 6^{2005^{2004^{\dots^{1}}}} \equiv 0\ (\text{mod}\ 2^3)

    Note that 6^{2005^{2004^{\dots^{1}}}} \equiv 1^{2005^{2004^{\dots^{1}}}} \equiv 1\ (\text{mod}\ 5)

    Now work backwards...

    CRT: 2006^{2005^{2004^{\dots^{1}}}} \equiv 16\ (\text{mod}\ 40)

    Euler: 2007^{2006^{2005^{\dots^{1}}}} \equiv 7^{16}  \equiv 1\ (\text{mod}\ 100)

    Euler: 2008^{2007^{2006^{\dots^{1}}}} \equiv 8^1\ \equiv 8\ (\text{mod}\ 5^3)

    CRT: 2008^{2007^{2006^{\dots^{1}}}} \equiv 8\ (\text{mod}\ 1000)

    So the answer is 008

    Just like Also sprach Zarathustra said!

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Ignore

    Quote Originally Posted by elemental View Post
    This is a very tricky question:
    Find the last three digits of
    2008^2007^2006^2005^...^1

    If you're having trouble thinking about how the exponents are arranged, just imagine every consecutive number a power of the previous.

    Good luck, I know the answer, and will tell you if you get it!
    Assuming you meant 2008^{2007^{2006^{2005^{2004...^{1}}}}}, call it P and let a=2007^{2006^{2005^{2004...^{1}}}} and b=2006^{2005^{2004...^{1}}}.

    I start with the fact that 2008\equiv 3\equiv -2(mod\ 5).

    b=2k for some integer k , so a=2007^b=2007^{2k}\equiv 3^{2k}\equiv 9^k\equiv 1(mod\ 4).
    a=4t+1 for some integer t , so (-2)^a=(-2)^{4t+1}=16^t(-2)\equiv-2(mod\ 5)

    Now, P=2008^a\equiv (-2)^a\equiv(-2)(mod\ 5). Also, obviously P is even, hence P\equiv -2(mod\ 2). These two congruences give P\equiv -2\equiv 8(mod\ 10).

    The last digit of 2008^{2007^{2006^{2005^{2004...^{1}}}}} is 8 .
    Last edited by melese; July 9th 2010 at 03:49 PM. Reason: RTQ (read the question)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    Well done guys, 008 is indeed correct.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Challenge questions belong in the Challenege Questions subforum (read the rules at that subforum before posting in it).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jan 2009
    Posts
    715
    We wish to find out the remainder when  2006^{2005^{...}} is divided by  40


    Let  x be  2006^{2005^{...}}

    then

     x \equiv 1 \bmod{5} and

     x \equiv 0 \bmod{8}  so

     \boxed{ x \equiv 16 \bmod{40} }



    Then consider  7^x in modulo  100

    it is  7^{40k + 16} \equiv 7^{16 }\bmod{100}

    Let  y = 7^{16 } we have

     y \equiv (-1)^{16} \equiv 1 \bmod{4} and

     y = 7^{16} = (49)^8 \equiv (-1)^8 \equiv 1 \bmod{25} so

     y \equiv 1 \bmod{100}


    Then  8^y  in modulo  125

    Since  (8,125) = 1 we have  8^{100} \equiv 1

    Therefore ,  8^y = 8^{100k + 1 } \equiv 8 \bmod{125}

    Together with  8^y \equiv 0 \bmod{8} we obtain  8^y \equiv 8 \bmod{1000}

    Actually , the answer is exactly 8 \equiv  8^y \equiv (2008)^y \bmod{1000}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 11th 2011, 09:50 PM
  2. A question on modular notation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 28th 2010, 01:16 AM
  3. Tricky (but interesting) question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 11th 2009, 05:57 AM
  4. Modular Question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 3rd 2009, 10:00 AM
  5. Modular solutions question
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: May 1st 2008, 12:45 PM

Search Tags


/mathhelpforum @mathhelpforum