# Math Help - Fermat's Theorem

1. ## 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!

2. ## Re: Fermat's Theorem

Originally Posted by romsek
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)

3. ## 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?

4. ## Re: Fermat's Theorem

Originally Posted by johng
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) ?

5. ## 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$$

6. ## 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)