Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By johng

Math Help - Fermat's Theorem

  1. #1
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    187

    Fermat's Theorem

    Find the remainder when x^100 + 2x + 10 is divided by x − 11 in Z17[x].


    Simplify the result using Fermatís theorem.

    I started to do long division, but it was not going well for me. I never have done Fermat's Theorem with this kind of problem before, so if someone could kind of tell me how to start this problem, I'd really appreciate it!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    187

    Re: Fermat's Theorem

    Quote Originally Posted by romsek View Post
    what does $x^{100} \pmod{17}$ equal?

    x^100 (mod 17)

    = (x^16)^6 * x^4 (mod 17)

    = (1)^6 * x^4 (mod 17)

    = x^4 (mod 17)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    713
    Thanks
    299

    Re: Fermat's Theorem

    So the remainder r satisfies:
    $$x^{100}+2x+10=(x-11)q(x)+r$$ for some polynomial $q(x)$ with coefficients in $\mathbb{Z}_{17}$. So $r=11^{100}+2\cdot11+10$ mod 17. Now can you finish?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    187

    Re: Fermat's Theorem

    Quote Originally Posted by johng View Post
    So the remainder r satisfies:
    $$x^{100}+2x+10=(x-11)q(x)+r$$ for some polynomial $q(x)$ with coefficients in $\mathbb{Z}_{17}$. So $r=11^{100}+2\cdot11+10$ mod 17. Now can you finish?

    How did you figure out that r = 11^100 + 2*11 + 10 (mod 17) ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    713
    Thanks
    299

    Re: Fermat's Theorem

    In the equation
    $$x^{100}+2x+10=(x−11)q(x)+r$$
    substitute x=11 to get
    $$11^{100}+2\cdot11+10=0\cdot q(11)+r=r$$
    Thanks from AwesomeHedgehog
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2013
    From
    Philadelphia
    Posts
    187

    Re: Fermat's Theorem

    Oh, alright. Thank you.

    This is what I did:

    Before solving 11^100 + 2*11 + 10, I had figured out earlier that x^100 (mod 17) = x^4 (mod 17)

    so, 11^100 (mod 17) = 11^4 (mod 17)

    inserting back into the equation, I got:

    11^4 + 22 + 10 = 14641 + 22 + 10 = 14673 = 2 (mod 17)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat Last Theorem
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: February 12th 2013, 09:27 PM
  2. Replies: 2
    Last Post: October 26th 2012, 04:35 AM
  3. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 30th 2009, 07:54 AM
  5. Fermat's Last Theorem
    Posted in the Advanced Math Topics Forum
    Replies: 13
    Last Post: July 21st 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum