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.


  • 1
    $\begingroup$ 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? $\endgroup$ – 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$: \begin{align} f &= x\cdot g+(x+1)\\ g &= (x+2)\cdot(x+1) + 2\\ (x+1) &= (2x)\cdot2 + 1 \end{align} Working backwards, we find \begin{align} 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. \end{align} So, the inverse of $g$ modulo $f$ is $h = x^3+2x^2 \pmod f = 2x^2+x+2 \pmod f$.

  • $\begingroup$ 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?) $\endgroup$ – David Chouinard Mar 25 '12 at 16:55
  • 1
    $\begingroup$ 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$.) $\endgroup$ – marlu Mar 25 '12 at 17:03
  • $\begingroup$ Pretty obvious, don't know why I missed that. Thanks. (@anon, marlu updated his response after I replied) $\endgroup$ – David Chouinard Mar 25 '12 at 17:11
  • $\begingroup$ @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. $\endgroup$ – anon Mar 25 '12 at 17:19
  • $\begingroup$ @BillDubuque: I edited my answer as soon as I noticed that the solution could be reduced modulo $f$. This was within five minutes after I posted the answer. Does this explain that there is no edit history? $\endgroup$ – marlu Mar 25 '12 at 17:59

This is very easy when using the augmented-matrix form of the extended Euclidean algorithm.

$\begin{eqnarray} (1)&& &&f = x^3\!+2x+1 &\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}0\,\right>\quad\ \ \, {\rm i.e.}\ \qquad f\, =\ \color{#c00}1\cdot f\, +\, \color{#0a0}0\cdot g\\ (2)&& &&\qquad\ \, g =x^2\!+1 &\!\!=&\, \left<\,\color{#c00}0,\,\color{#0a0}1\,\right>\quad\ \ \,{\rm i.e.}\ \qquad g\, =\ \color{#c00}0\cdot f\, +\, \color{#0a0}1\cdot g\\ (3)&=&(1)-x(2)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\ \ x+1 \,&\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}{-x}\,\right>\ \ \ {\rm i.e.}\quad x\!+\!1\, =\, \color{#c00}1\cdot f\,\color{#0c0}{-\,x}\cdot g\\ (4)&=&(2)+(1\!-\!x)(3)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ 2 \,&\!\!=&\, \left<\,\color{#c00}{1\!-\!x},\,\color{#0a0}{1\!-\!x+x^2}\,\right>\\ \end{eqnarray}$

Hence the prior line implies: $\,\ 2\, =\, (\color{#c00}{1\!-\!x})f + (\color{#0a0}{1\!-\!x\!+\!x^2})g $

Thus in $\,\Bbb Z_3[x] \bmod f\!:\,\ {-}1\equiv 2 \equiv (\color{#0a0}{1\!-\!x\!+\!x^2})g\ \Rightarrow\ \bbox[6px,border:1px solid red]{g^{-1}\equiv\, {-}(\color{#0a0}{1\!-\!x\!+\!x^2})}$

Remark $\ $ Generally, this method is easier to memorize and much less error-prone than the alternative "back-substitution" method.

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.

  • $\begingroup$ 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? $\endgroup$ – David Chouinard Mar 25 '12 at 16:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Mar 25 '12 at 16:50
  • $\begingroup$ Understood, thanks. $\endgroup$ – David Chouinard Mar 25 '12 at 17:00
  • $\begingroup$ See here for another worked example. $\endgroup$ – Bill Dubuque Jul 1 '17 at 19:57

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$.

  • $\begingroup$ 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. $\endgroup$ – 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.


With the following identity, I would claim that the modular inverse of $(1 + x^2) \mod (1 + 2 x + x^3)$ is $1/2 (2 + x + x^2 + x^3)$, provided that $x$ is even.

$$1/2 (2 + x + x^2 + x^3) (1 + x^2) - 1/2 x (1 + x) (1 + 2 x + x^3) = 1$$

For example, if $x =20$, then $1 + x^2 = 401$, $1 + 2 x + x^3 = 8041$, $1/2 (2 + x + x^2 + x^3) = 4211$, and $(401)^(-1) mod 8041 = 4211$.

  • 1
    $\begingroup$ Welcome to MathSE! Please see the site's LaTeX tutorial, which will help you to format your posts. $\endgroup$ – ncmathsadist Oct 15 '14 at 14:45
  • 1
    $\begingroup$ $x$ is an indeterminate. It is neither even nor odd. It has no "value". The congruences here are in the polynomial ring. $\endgroup$ – Jyrki Lahtonen Oct 15 '14 at 15:35

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.