# Finding inverse of polynomial in a field

I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take:

In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + 1$.

My understanding is that one needs to use the (Extended?) Euclidean Algorithm and Bezout's Identity. Here's what I currently have:

Proceeding with Euclid's algorithm:

$$x^3 + 2x + 1 =(x^2 + 1)(x) + (x + 1) \\\\ x^2 + 1 = (x + 1)(2 + x) + 2$$

We stop here because 2 is invertible in $\mathbb{Z}_3[x]$. We rewrite it using a congruence:

$$(x+1)(2+x) \equiv 2 mod(x^2+1)$$

I don't understand the high level concepts sufficiently well and I'm lost from here. Thoughts?

Wikipedia has a page on this we a decent explanation, but it's still not clear in my mind.

Note that this question has almost the same title, but it's a level of abstraction higher. It doesn't help me, as I don't understand the basic concepts.

Thanks.

-
If you can write $2$ as $(x^3+2x+1)f(x)+(x^2+1)g(x)$, then $2g(x)$ is an inverse to $x^2+1$ in $\mathbb Z_3[x]/(x^3+2x+1)$. Does it help? –  Pierre-Yves Gaillard Mar 25 '12 at 16:20

Write $f := x^3+2x+1$ and $g := x^2+1$. We want to find the inverse of $g$ in the field $\mathbb F_3[x]/(f)$ (I prefer to write $\mathbb F_3$ instead of $\mathbb Z_3$ to avoid confusion with the 3-adic integers), i.e. we are looking for a polynomial $h$ such that $gh \equiv 1 \pmod f$, or equivalently $gh+kf=1$ for some $k\in \mathbb F_3[x]$. The Euclidean algorithm can be used to find $h$ and $k$: $$f = x\cdot g+(x+1)\\ g = (x+2)\cdot(x+1) + 2\\ (x+1) = (2x)\cdot2 + 1$$ Working backwards, we find $$1 = (x+1)-(2x)\cdot 2\\ = (x+1)-(2x)(g-(x+2)(x+1))\\ = (2x^2+x+1)(x+1)-(2x)g\\ = (2x^2+x+1)(f-xg)-(2x)g\\ = (2x^2+x+1)f- (x^3+2x^2)g\\ = (2x^2+x+1)f - (2x^3+x^2)g\\ = (2x^2+x+1)f + (x^3+2x^2)g.$$ So, the inverse of $g$ modulo $f$ is $h = x^3+2x^2 \pmod f = 2x^2+x+2 \pmod f$.

-
Great, I understand. Thank you. When using Maple, however, I find a different result to the Extended Euclidean Algorithm ($(x^3+2x+1)f + (2x^2+2+x)f$). Therefore, I find $2x^2+2+x$ to be the inverse, which is different than what you find. Is this normal? (integers only have one inverse, is this different for polynomials?) –  David Chouinard Mar 25 '12 at 16:55
You are right, there is only one inverse. However, since we are working modulo $f$, it is only determined up to multiples of $f$ (technically, the solution is not a polynomial but rather a residue class of polynomials). Note that $(x^3+2x^2) = (2x^2+x+2)+f$, so the solutions are in fact equivalent. (I just edited my answer to include also the reduced solution $2x^2+x+2$.) –  marlu Mar 25 '12 at 17:03
Pretty obvious, don't know why I missed that. Thanks. (@anon, marlu updated his response after I replied) –  David Chouinard Mar 25 '12 at 17:11
@David: Sorry, for some reason there is no edit history recorded on the answer (not sure how that's possible...), so I didn't know it was edited. –  anon Mar 25 '12 at 17:19
@anon Yes, that's strange. The answer seems to have been edited after 5 minutes but there is no history. I've flagged for mods, in case there may be a bug. –  Bill Dubuque Mar 25 '12 at 17:41

The goal of the Extended Euclidean algorithm is to compute polynomials $\rm\:A,B\:$ such that $\rm\: A\: (x^2+1)\: +\: B\:(x^3+2x+1) = 1.\:$ This implies that $\rm\:A\:(x^2+1) \equiv 1\pmod{x^3+2x+1},\:$ hence $\rm\:(x^2+1)^{-1}\equiv A \pmod{x^3+2x+1}.\:$

Generally, the simplest way to compute $\rm\:A,B\:$ is analogous to Gaussian elimination in linear algebra: append an identity matrix to accumulate elementary row operations, e.g. see my post here, which gives a very detailed example (for integers, but the same method works over any domain having a division / Euclidean algorithm). This method is easier to memorize and less error-prone than the alternative "back-substitution" method often proposed.

This is a special-case of Hermite/Smith row/column reduction of matrices to triangular/diagonal normal form, using the division/Euclidean algorithm to reduce entries modulo pivots. Though one can understand this knowing only the analogous linear algebra elimination techniques, it will become clearer when one studies modules - which, informally, generalize vector spaces by allowing coefficients from rings vs. fields. In particular, these results are studied when one studies normal forms for finitely-generated modules over a PID, e.g. when one studies linear systems of equations with coefficients in the non-field! polynomial ring $\rm F[x],$ for $\rm F$ a field, as above.

-
Yes, this makes a lot of sense. In this case, I found $A = 2x^2+2+x$ and $B = (x^3+2x+1)$. Therefore, $2x^2+2+x$ is the inverse. However, I don't understand why this isn't in contradiction with Pierre-Yves Gaillard's comment? –  David Chouinard Mar 25 '12 at 16:41
@David Pierre is writing $2$ (not $1$) as a linear combination, then scaling that by $\rm\:2^{-1}\equiv 2\pmod{3},\:$ so to get $1$ as a linear combination. –  Bill Dubuque Mar 25 '12 at 16:50
Understood, thanks. –  David Chouinard Mar 25 '12 at 17:00

The same algorithm used to solve the linear diophantine equation can be used here. $$\begin{array}{c} &&x&x-1&(x+1)/2\\ \hline 1&0&1&1-x&(x^2+1)/2\\ 0&1&-x&x^2-x+1&-(x^3+2x+1)/2\\ x^3+2x+1&x^2+1&x+1&2&0 \end{array}$$ Thus, $$(1-x)(x^3+2x+1)+(x^2-x+1)(x^2+1)=2$$ Thus, the inverse of $x^2+1$ is $\tfrac12(x^2-x+1)$ mod $x^3+2x+1$.

-
That's the same as the method I mentioned - which is more conceptually viewed from a linear algebra (module) perspective, where it is a special case of Hermite/Smith row/column reduction of matrices to triangular/diagonal normal form, using the division/Euclidean algorithm to reduce entries mod pivots. –  Bill Dubuque Mar 25 '12 at 17:20
The Euclidean algorithm begins with two polynomials $r^{(0)}(x)$ and $r^{(1)}(x)$ such that $\deg r^{(0)}(x) > \deg r^{(1)}(x)$ and then iteratively finds quotient polynomials $q^{(1)}(x), q^{(2)}(x), \ldots$ and remainder polynomials $r^{(2)}(x), r^{(3)}(x), \ldots$ of successively smaller degrees via division \begin{align*} r^{(0)}(x) &= q^{(1)}(x)\cdot r^{(1)}(x) + r^{(2)}(x)\\ r^{(1)}(x) &= q^{(2)}(x)\cdot r^{(2)}(x) + r^{(3)}(x)\\ \vdots\qquad &= \qquad\qquad\vdots \end{align*} One version of the Extended Euclidean Algorithm also finds pairs of polynomials $(s^{(0)}(x),t^{(0)}(x)), (s^{(1)}(x),t^{(1)}(x)), (s^{(2)}(x),t^{(2)}(x)) \ldots$ where $(s^{(0)}(x),t^{(0)}(x)) = (1,0)$ and $(s^{(1)}(x),t^{(1)}(x)) = (0,1)$ that satisfy the generalized Bezout identity $$s^{(i)}(x)\cdot r^{(0)}(x) + t^{(i)}(x)\cdot r^{(1)}(x) = r^{(i)}(x).$$
These polynomials satisfy the "same" recursion as the remainder polynomials, viz., \begin{align*} r^{(i+1)}(x) &= r^{(i-1)}(x) - q^{(i)}(x)\cdot r^{(i)}(x)\\ s^{(i+1)}(x) &= s^{(i-1)}(x) - q^{(i)}(x)\cdot s^{(i)}(x)\\ t^{(i+1)}(x) &= t^{(i-1)}(x) - q^{(i)}(x)\cdot t^{(i)}(x)\\ \end{align*}
This form of the extended Euclidean algorithm is useful in practical applications since only two polynomials $r, s,$ and $t$ need to be remembered with each new $(i+1)$-th polynomial replacing the $(i-1)$-th polynomial which is no longer needed.
In your instance, you have $r^{(0)}(x) = x^3 + 2x+1$ and $r^{(1)}(x) = x^2 + 1$. You have already computed the quotient and remainder sequence ending with $r^{(3)}(x) = 2$. Now compute $t^{(2)}(x)$ and $t^{(3)}(x)$ iteratively using the sequence of quotient polynomials and write \begin{align*} s^{(3)}(x)\cdot (x^3 + 2x + 1) + t^{(3)}(x)\cdot(x^2 + 1) &= 2\\ -s^{(3)}(x)\cdot (x^3 + 2x + 1) - t^{(3)}(x)\cdot(x^2 + 1) &= 1\\ (-t^{(3)}(x))\cdot (x^2 + 1) &= 1 ~ \mod (x^3 + 2x + 1) \end{align*} and deduce that the multiplicative inverse of $x^2 + 1$ in $\mathbb Z_3[x]/(x^3 + 2x + 1)$ is $-t^{(3)}(x)$. Note that the $s^{(i)}(x)$ sequence does not need to be computed at all if all that one needs is the inverse.