# Is there a good way to solve for the inverse of $(u^2-u+4)$?

I'm having trouble calculating the inverse of a polynomial. Consider the polynomial $f(x)=x^3+3x-2$, which is irreducible over $\mathbb{Q}$, as it has no rational roots. So $\mathbb{Q}[x]/(f(x))\simeq \mathbb{Q}[u]$ is a field.

How would I calculate $(u^2-u+4)^{-1}$ as a polynomial? Calling this $p(u)$, I tried solving for it by writing $$p(x)(x^2-x+4)=q(x)f(x)+1$$ but I don't know what $q(x)$ is. How can I write down $(u^2-u+4)^{-1}$ explicitly? Thanks.

-
Using Extended euclidean algorithm is a possible way. – Aang Jul 11 '12 at 5:16

Let's calculate the $\gcd$ of the two polynomials $x^3+3x-2$ and $x^2-x+4$ in $\mathbb{Q}[x]$. Using the Euclidean algorithm, $$x^3+3x-2=x(x^2-x+4)+(x^2-x-2)$$ $$x^2-x+4=(x^2-x-2)+6$$ Because $2$ is a unit in $\mathbb{Q}[x]$, we see that the polynomials are relatively prime. Now, building back up, we see that $$6=(x^2-x+4)-(x^2-x-2)$$ $$6=(x^2-x+4)-[(x^3+3x-2)-x(x^2-x+4)]$$ $$6=(-1)(x^3+3x-2)+(1+x)(x^2-x+4)$$ $$1=\left(-\tfrac{1}{6}\right)(x^3+3x-2)+\left(\tfrac{1+x}{6}\right)(x^2-x+4)$$ Plugging in $u$, which is a root of $x^3+3x-2$, we see that $$1=\left(\tfrac{1+u}{6}\right)(u^2-u+4)$$ so that $\tfrac{1+u}{6}$ is the multiplicative inverse of $u^2-u+4$ in $\mathbb{Q}(u)$.

-
Thanks Zev! I got $x^3+3x-2=(x+1)(x^2-x+4)-6$, and then solving I found $(u^2-u+4)^{-1}=\frac{1+u}{6}$. Did I do something wrong, or are they the same? – Son Bi Jul 11 '12 at 5:34
Whoops, looks like I made some arithmetic errors - your result is correct. I'll edit my answer! – Zev Chonoles Jul 11 '12 at 5:36

You want $$(u^2-u+4)(au^2+bu+c)=1$$ Multiply the left side out, using $u^3=2-3u$ and $u^2=2u-3u^2$ to reduce the left side to a polynomial of degree 2 with coefficients involving the unknowns $a,b,c$. The right side is also a polynomial of degree 2; it's $1+0u+0u^2$. Setting coefficients equal gives you three linear equations in $a,b,c$.
Hint $\$ By the polynomial long division algorithm $$\begin{eqnarray}\rm x^3 + 3\, x -2 &=&\rm\ (x+1)\, (x^2-x+4)\, -\, \color{#C00}6 \\ \Rightarrow\ \ \rm mod\ \ x^3+3\,x - 2\!:\!\! & &\rm\ \dfrac{x+1}{\color{#C00}6} \ (x^2-x+4)\,\equiv\, 1 \end{eqnarray}$$
Remark $\$ There is no need to apply the hairy extended Euclidean algorithm machinery in such simple cases as this, where $\rm\:f\ mod\ g\:$ is $\rm\color{#C00}{constant}$, since we can "read off" the inverse immediately as above from a single division (i.e. the Euclidean algorithm terminates in one step for such cases, so it reduces to the division algorithm). This optimization of the extended euclidean algorithm occurs frequently in practice (by law of small numbers) so it is well-worth knowing and checking.