3
$\begingroup$

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:

enter image description here

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

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

$\ \ {\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}$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I likes your colorful short answer. +1 $\endgroup$ – Bumblebee Apr 27 '15 at 6:27
  • $\begingroup$ So the answer in the original question (12) is incorrect? Did I enter it into Mathematica wrong? $\endgroup$ – user1282637 Apr 29 '15 at 0:01
  • 1
    $\begingroup$ @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\ \ $ $\endgroup$ – Gone Apr 29 '15 at 0:11
  • $\begingroup$ Ahhh I see, ok thank you for the help! $\endgroup$ – user1282637 Apr 29 '15 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.