# Find the remainder when $x^{100} + 2x + 10$ is divided by $x − 11$ in $\mathbb Z_{17}[x]$

Find the remainder when $x^{100} + 2x + 10$ is divided by $x − 11$ in $\mathbb Z_{17}[x]$

I simplified

$x^{100} + 2x + 10$ to $x^{15} + 2x + 10$

and $x − 11$ to $x+6$ to be in $\mathbb Z_{17}$.

I got stuck here and used Mathematica and got this answer:

Is there any way to get this remainder without actually diving x+6 into $x^{15} + 2x + 10$?

• The remainder is $12=11^{100}+2\cdot 11+10$ (little Bézout's theorem) and the monstrous polynomial is the quotient :) – Alexey Burdin Apr 27 '15 at 3:06

$\ \ {\rm mod}\ \color{#c00}{17},\, \color{#0a0}{x\!-\!11}\!:\,\ \color{#0a0}{x\equiv 11}\,\Rightarrow\,\color{#0a0}x^{\large \color{#a0f}{100}}\equiv {\color{#0a0}{11}}^{100}\equiv \overbrace{11^4(\color{#c00}{11^{\color{#c00}16}})^6\equiv (-6)^4\color{#c00}1^6}^{\rm little\ \color{#c00}{Fermat}}\equiv 2^2\equiv \color{#a0f}{4}$
Therefore we conclude \quad \begin{align} &{\color{#0a0}{x}}^{\large\color{#a0f}{100}}+2\color{#0a0}x+10\\ \ \ \equiv \ \ \ &\color{#a0f}4+\,2\,(\color{#0a0}{11})+10\equiv 36\equiv 2\end{align}
• @user1282637 It's wrong because $\,x^{100}\not\equiv x^{15}.\,$ Rather, $\, j\equiv k\pmod{16}\,\Rightarrow$ $\,{\rm mod}\ 17\!:\ x^j\equiv x^k\,$ if $\,x\not\equiv 0\ \$ – Gone Apr 29 '15 at 0:11