Results 1 to 3 of 3

Math Help - Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    17

    Unhappy Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

    Hey guys,

    Im confused with this :s

    Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

    We're dealing with a huge power, and it confused me as to how I am supposed to work it out.

    I could start with doing

    7 = 7 mod 1000
    7^2 = 49 mod 1000
    7^3 = 343 mod 1000
    7^4 = 401 mod 1000

    and maybe work it out with multiples of them? But then again the number (8^9) is huge so it might not be practical.

    I was thinking of using Fermats Little Theorem, but I am unsure as to where I should begin.

    Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Since 7 is coprime with 1000, by the Euler's theorem, 7^{\varphi(1000)}\equiv1\pmod{1000}, where \varphi(n) is Euler's totient function. The last link shows that \varphi(1000)=\varphi(2^3\cdot5^3)=1\cdot2^2\cdot4  \cdot5^2=400.

    So, the first step is to find the remainder of 8^9 and 400. I got 128. Next, we need to find the remainder of 7^{128} and 1000. I did the following: 7^{128}=49^{64}=2401^{32}\equiv401^{32}\equiv801^{  16}\equiv\dots\equiv801\pmod{1000}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    17
    Thanks a lot!

    I understand it perfectly now thank you again!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 5th 2011, 12:27 PM
  2. [SOLVED] Remainder when large numbers divided
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 27th 2011, 06:13 PM
  3. remainder when divided by 7
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 14th 2011, 04:43 AM
  4. what is the remainder of the summation when divided by ten
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: July 24th 2010, 02:51 AM
  5. remainder of sum, divided by 4
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 6th 2008, 12:50 PM

Search Tags


/mathhelpforum @mathhelpforum