Results 1 to 9 of 9

Math Help - Fermat"s Theorem

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    79

    Fermat"s Theorem

    What are the possible remainders when
    Fn (the nth Fermat number Fn := 2^2n + 1,

    n
    1) is divided by (a). 3, (b). 7, (c). 9?

    I know the Fermat number is defined as 2^(2n)+1, but have trouble in finding possible remainders.

    Like I can find F_0=2^0+1=2, so remainder when dived by 3 is 1, 5 when divided by 7, 7 when divided by 9
    I guess I could continue in this method, but might there be an easier way to do this?

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,843
    Thanks
    320
    Awards
    1
    Quote Originally Posted by mathematic View Post
    What are the possible remainders when
    Fn (the nth Fermat number Fn := 2^2n + 1,

    n
    1) is divided by (a). 3, (b). 7, (c). 9?

    I know the Fermat number is defined as 2^(2n)+1, but have trouble in finding possible remainders.

    Like I can find F_0=2^0+1=2, so remainder when dived by 3 is 1, 5 when divided by 7, 7 when divided by 9
    I guess I could continue in this method, but might there be an easier way to do this?

    I can help with a) and b), but I'm not certain of my method for c) because 9 is not a prime. (I haven't actually tried it in mod 9.)

    Since 2 \equiv -1 ~\text{(mod 3)}

    \dsiplaystyle 2^{2n} + 1 \equiv (-1)^{2n} + 1 \equiv 1^{n} + 1 \equiv 1 + 1 \equiv 2 ~\text{(mod 3)}

    So 2 is the only remainder.

    You can do this for part b) as well. I get possible remainders of 2, 3, and 5.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2011
    Posts
    79
    2=2 mod 7
    so (2)^(2n)+1=2^2*2^n+1=4*2^n+1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,843
    Thanks
    320
    Awards
    1
    Here's the corrected version.

    \displaystyle F_n = 2^{2^n}+1

    mod 3:

    2^n \equiv \{1,~2 \}~\text{(mod 3)}

    Thus
    2^{2^n} + 1 \equiv 2^{2^1} + 1 \equiv 2

    or
    2^{2^n} + 1 \equiv 2^{2^2} + 1 \equiv 2


    The process for mod 7 is similar. I get 3, 5 for answers now. Again I don't know how to approach mod 9.

    -Dan

    Of course this is all for n > 0...
    Last edited by topsquark; March 16th 2011 at 06:13 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2011
    Posts
    79
    2^1=1 mod7
    2^2=4 mod 7
    2^3=8=1 mod 7
    2^4=16=2 mod 7
    2^5=32=4 mod 7
    2^6=64=1 mod 7
    2^7=128=2 mod 7
    so 2^n={1,2,4} mod 7

    2^(2^1)+1=2^2+1=4+1=5mod 7
    2^(2^2)+1=2^4+1=16+1=17=3 mod 7
    2^(2^4)+1=2^16+1=65,356+1=65,357=2 mod 7

    For 9
    2^1=2 mod 9
    2^2=4 mod 9
    2^3=8 mod 9
    2^4=16=7mod9
    2^5=32=5 mod 9
    2^6=64=1 mod 9
    2^7=2 mod 9
    2^8=4 mod 9
    2^9=8 mod 9
    So 2^n={1,2,4,5,7,8}
    2^(2^1)+1=4+1=5 mod 9
    2^(2^2)+1=16+1=17=8 mod 9
    2^(2^4)+1=8 mod 9
    2^(2^5)+1=5 mod9
    2^(2^7)+1=
    so remainders are 5 and 8
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,843
    Thanks
    320
    Awards
    1
    Quote Originally Posted by mathematic View Post
    2^(2^4)+1=2^16+1=65,356+1=65,357=2 mod 7
    65537 = 3 (mod 7)

    -Dan
    Last edited by topsquark; March 16th 2011 at 07:52 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2011
    Posts
    79
    i rechecked and now I'm getting 65,357=5 mod 7
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jan 2011
    Posts
    79
    oh, it should be 65,537
    ok i get 3 now
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,843
    Thanks
    320
    Awards
    1
    Quote Originally Posted by mathematic View Post
    For 9
    2^1=2 mod 9
    2^2=4 mod 9
    2^3=8 mod 9
    2^4=16=7mod9
    2^5=32=5 mod 9
    2^6=64=1 mod 9
    2^7=2 mod 9
    2^8=4 mod 9
    2^9=8 mod 9
    So 2^n={1,2,4,5,7,8}
    2^(2^1)+1=4+1=5 mod 9
    2^(2^2)+1=16+1=17=8 mod 9
    2^(2^4)+1=8 mod 9
    2^(2^5)+1=5 mod9
    2^(2^7)+1=
    so remainders are 5 and 8
    It is, of course, possible to do it this way, but I was hoping to find something more efficient given that 9 = 3*3. But it does work.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 13th 2008, 06:30 AM
  3. Not Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 10:39 PM
  4. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM
  5. Fermat's little theorem
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 19th 2007, 09:23 PM

Search Tags


/mathhelpforum @mathhelpforum