Results 1 to 2 of 2

Math Help - fermat's little thm

  1. #1
    Junior Member
    Joined
    May 2008
    Posts
    70

    fermat's little thm

    compute the remainder when 2^(2^17) + 1 = 19

    that + 1 is really throwing me off... I don't know how to deal with it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Coda202 View Post
    compute the remainder when 2^(2^17) + 1 = 19

    that + 1 is really throwing me off... I don't know how to deal with it.
    I assume you want to find the remainder of 2^{2^{17}}+1 modulo 19.

    By the division algorithm we can write 2^{17} = 18q + r where 0\leq r < 18.
    But then, 2^{2^{17}} = 2^{18q + r} = \left( 2^{18} \right)^q \cdot 2^r \equiv 2^r (\bmod 19).

    To find the remainder r we need to simplify 2^{17} modulo 18.
    First, 2^{\phi(9)} \equiv 1(\bmod 9) \implies 2^6\equiv 1(\bmod 9) \implies 4\cdot 2^{16} \equiv 1(\bmod 9).
    Multiply both sides by seven to get, 2^{16}\equiv 7(\bmod 9) \implies 2^{17}\equiv 14(\bmod 18).

    Therefore, 2^{2^{17}}\equiv 2^{14} (\bmod 19).

    Now, 16\cdot 2^{14}\equiv 1(\bmod 19) by Fermat's little theorem.
    Since 16\cdot 6\equiv 1(\bmod 19) we see that 2^{14} \equiv 6(\bmod 19).

    But this is remainder of only 2^{2^{17}} if you want to find remainder of 2^{2^{17}}+1 just add 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's little theorem help!
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 17th 2011, 09:16 PM
  2. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 10:47 PM
  3. Not Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 11:39 PM
  4. Fermat's
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 24th 2008, 07:36 PM
  5. fermat...or not fermat?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2006, 10:16 AM

Search Tags


/mathhelpforum @mathhelpforum