1

Let a polynomial be given by

$$P(x) = 3x^{12n+5}+x^{3}+1$$

What is the remainder of the division of $P(x)$ by $x^2+x+1$?

As suggested in comments, we start off with observing that

$$x^3-1\equiv 0\pmod{x^2+x+1}\tag{1}$$

$$x^2\equiv -(x+1)\pmod{x^2+x+1}\tag{2}$$

From which we can conclude that

$$\begin{align}P(x) = 3x^{12n+5}+x^3+1&\equiv 3x^3x^{12n+2} + 2\pmod{x^2+x+1} \\ &\equiv 3x^{12n+2}+2\pmod{x^2+x+1} \\ &\equiv 3x^2(x^{3})^4+2\pmod{x^2+x+1} \\ &\equiv 3x^2+2\pmod{x^2+x+1}\\ &\equiv -3(x+1)+2\pmod{x^2+x+1}\\&= -3x-1\pmod{x^2+x+1}\end{align}$$

  • I can't be much help, but I noticed that in the last equation you wrote $3x(-x+1)^{6n+2}$ and it should be $3x(x+1 )^{6n+2}$. Another thing is that $-x(x+1)+1=-x^2-x+1$ and try to figure out what its reminder of $x^2+x+1$ and it may help you a bit more. – Ariel Fishbein Sep 09 '23 at 18:23
  • @ArielFishbein No problem, please. Thank you very much for your so valuable correction! –  Sep 09 '23 at 18:24
  • 3
    $x^2 + x + 1$ divides $x^3-1$. That should help simplify it. – Tony Pizza Sep 09 '23 at 18:25
  • 2
    First find the remainder mod $x^3-1.$ To get rid of $n$ observe that $x^{12n+3}-1$ is divisible by $x^3-1.$ – Ryszard Szwarc Sep 09 '23 at 18:26
  • You can do it slightly faster: $3x^{12n+5}=3x^2(x^3)^{4n+1}=3x^2$ mod $x^2+x+1.$ – Ryszard Szwarc Sep 09 '23 at 19:06
  • @RyszardSzwarc Sure, that makes perfect sense! –  Sep 09 '23 at 19:08

2 Answers2

4

Another way to do it is noticing that remainder will be of form Ax+B, Using euclidean algorithm

$3x^{12n+5}+x^{3}+1=(x^2+x+1)(g(x))+Ax+B$

first putting $x=w$,where $w$ is one of cube roots of unity

$3(w^2)+1+1=0+Aw+B$ ......as $w^2+w+1=0$

$3(w^2)+2=Aw+B$ ......(1)

now putting $x=w^2$,where $w^2$ is another cube root of unity

$3(w)+1+1=0+Aw^2+B$

$3(w)+2=Aw^2+B$.......(2)

solving for A and B using equations (1) and (2) results in $A=-3,B=-1$

Hence Remainder will be $-3x-1$

Dheeraj Gujrathi
  • 1,036
  • 4
  • 20
1

In this very particular case we can use another method by applying the complex root $z=-{1\over 2}+i{\sqrt{3}\over 2}$ of the polynomial $x^2+x+1,$ which at the same time is a root of $x^3-1,$ i.e. satisfies $z^3=1.$ Moreover $z\overline{z}=1.$ Let $$P(x)=3x^{12n+6}x^{-1}+x^3+1=ax+b\quad ({\rm mod}\, x^2+x+1)$$ Plugging in $x=z$ gives $$3\overline{z}+2=az+b \quad (*)$$ and by the complex conjugation $$3z+2=a\overline{z}+b$$ Subtracting the equations gives $$(z-\overline{z})(a+3)=i\sqrt{3}(a+3)=0$$ hence $a=-3.$ By taking the real part of $(*)$ we obtain $$-{3\over 2}+2=-{a\over 2}+b={3\over 2}+b$$ Thus $b=-1.$

Ryszard Szwarc
  • 30,319
  • First of all $e^{4\pi i\over 3}=-{1\over 2}-i{\sqrt{3}\over 2}.$ I am applying the root $z=e^{2\pi i\over 3}=-{1\over 2}+i{\sqrt{3}\over 2}$ and the properties $z^3=1$ and $z^{-1}=\overline{z}.$ – Ryszard Szwarc Sep 09 '23 at 20:15
  • My apologies, yes, that's true. –  Sep 09 '23 at 20:16