Results 1 to 9 of 9

Math Help - fermat's little theorem

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    fermat's little theorem

    find the remain 17der of 36^(50) + 31^(19) when divided by 17, i got 9 for this but apparently the answer is 11, thanks for any help
    Last edited by hmmmm; May 15th 2010 at 04:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Have you actually used fermat's Little theorem?

    It states that for any prime number p we have a^{p-1}\equiv 1 mod p

    Here we divide by p=17, thus we have a^{16}\equiv 1 mod 17 for any number a.

    Use this fact and observe that 36^{50}\equiv 2^{50} \equiv (*) 2^{2} \equiv 4 mod 17

    (*) here we used fermat's theorem.

    Now you try 30^{19} mod 17
    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 hmmmm View Post
    find the remain 17der of 36^(50) + 30^(19) when divided by 17, i got 9 for this but apparently the answer is 11, thanks for any help
    36^{50} + 30^{19} \equiv 2^{50} + 13^{19} \equiv 2^{3\cdot16+2}+13^{16+3} \equiv 2^2+13^3\equiv4+2197\equiv8\ \text{(mod }17\text{)}

    The book answer is 11? I did a direct calculation and also got 8.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    36^{50} + 30^{19} \equiv 2^{50} + 13^{19} \equiv 2^{3\cdot16+2}+13^{16+3} \equiv 2^2+13^3\equiv4+2197\equiv8\ \text{(mod }17\text{)}
    The book answer is 11? I did a direct calculation and also got 8.


    Yeah me too, 11 is definately wrong!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    ok i've checked my answer an i think i made a stupid mistake at the end,

    36= 2 mod 17 and 31 = -3 mod 17 therefore

    36^(50) + 30^(19) = ( 2^50 + ((-3)^19 ) mod 17
    = (1 + -27) mod 17 using fermat's little theorem
    = 8 mod 17
    therefore the remainder is 8 (i had 9 here instead making a stupid mistake) is this correct then,

    really sorry i dont know how to use latex yet but i have my exams soon so im busy revising, thanks for any help
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    ok i've checked my answer an i think i made a stupid mistake at the end,

    36= 2 mod 17 and 31 = -3 mod 17 therefore

    36^(50) + 30^(19) = ( 2^50 + ((-3)^19 ) mod 17
    = (1 + -27) mod 17 using fermat's little theorem
    = 8 mod 17
    therefore the remainder is 8 (i had 9 here instead making a stupid mistake) is this correct then,

    really sorry i dont know how to use latex yet but i have my exams soon so im busy revising, thanks for any help
    Is it 36^{50} + 3\color{red}0\color{black}^{19} or 36^{50} + 3\color{red}1\color{black}^{19} ??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    oh dear sorry its 31
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by hmmmm View Post
    oh dear sorry its 31
    Ah, it's clear now.

    -27 is fine. This becomes 7 (mod 17). But where you wrote 1 + -27, it should be 4 + -27. See above posts. Then 4 + 7 = 11.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    ah ok thanks very much sorry about that
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 17th 2011, 02:09 AM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: February 24th 2010, 06:56 PM
  4. Fermat's Little Theorem Help
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 27th 2008, 10:13 AM
  5. Fermatís Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 25th 2008, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum