Find polynomials $r(x)$ and $s(x)$ such that $r(x)(x^2+x+1)+s(x)(x^3-x-1)=1$.

Question

I realize this has something to do with the Euclidean algorithm over $\mathbb{Q}[x]$, and I know how to show that the $\gcd(x^2+x+1, x^3-x-1)=1$, but I have no idea where to even begin looking for polynomials satisfying the Euclidean algorithm.

Is it largely just trial and error? Or is there some methodic process that I can go about solving for these polynomials...

Answer 1

Let $p(x) = x^{2}+x+1$ and $q(x) = x^{3}-x-1$.

Then if we divide, we have $q(x) = (x-1)\cdot p(x) - x$.

Then we divide $p(x)$ with $-x$, we have $p(x) = (-x-1)\cdot (-x) + 1$.

Thus

$$-x = q(x) - (x-1)\cdot p(x),$$ i.e., $$1 = p(x) - (-x-1)\cdot(-x).$$

Then $$\begin{align}1 &= p(x) - (-x-1)\cdot (q(x)-(x-1)\cdot p(x))\\ &= (x+1)\cdot q(x) + ((-x-1)\cdot (x-1)+1)\cdot p(x).\end{align}$$

Just take $s(x) = x+1$, and $r(x) = -x^{2}+2$.

Answer 2

Another way. You know from inspection that the degree of $r(x)$ has to be exactly one higher than that of $s(x)$.

By substituting $x= \omega$ and $x = \overline \omega$ in turn (the conjugate complex roots of one), the term with $x^2 + x+1$ vanishes, and you immediately get:

$s(\omega) = - \frac 1{\omega} = \omega +1$

and $s(\overline \omega) = \overline \omega + 1$

which is consistent with a linear polynomial $s(x) = x+1$

We now need to test if we can get a consistent quadratic solution for $r(x)$ corresponding to this, then the problem is solved.

By inspection, the lead term for $r(x) = - x^2$ and the constant term is $2$. All we need is the middle term, let its coefficient be $b$, i.e. $r(x) = -x^2 +bx+2$.

Expanding, we get:

$-x^4 +x^3(b-1)+x^2(b+1)+x(b+2)+2 + x^4 +x^3-x^2-2x-1 =1$

which immediately allows us to conclude that $b=0$ is a consistent solution.

This gives $r(x) = -x^2 +2,\ s(x)=x+1$.

Answer 3

It's trivial using the method of simpler multiples. Let $\,g = x^3\!-\!x\!-\!1.\,$ Note $\,f = x^2\!+\!x\!+\!1\,$ has simpler multiple $\,\color{#0a0}{h = x^3\!-\!1}\,$ so $\, r\:\!f + s\,g = 1\iff \bmod f\!:\ s\,g\equiv 1\iff s\equiv 1/g,\,$ which we compute first modulo the simpler multiple $\,\color{#0a0}{h},\,$ i.e. $\,1/g \bmod f = (1/g \bmod \color{#0a0}{x^3\!-\!1})\bmod f,\,$ i.e.

$$\bmod \color{#c00}{x^2\!+\!x}\!+\!1\!:\,\ \dfrac{1}{g}\,\equiv\, \dfrac{1}{\color{#0a0}{x^3\!-\!1}\!-\!x\bmod \color{#0a0}{x^3\!-\!1}}\,\equiv\, \dfrac{-(\color{#c00}{x^2+x})}{-x}\,\equiv\, x+1\qquad $$

Remark $ $ The method in Deepak's answer is essentially the same but instead replaces arithmetic $\bmod f\,$ by equivalent calculations using the roots of $\,f.$