13
$\begingroup$

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.

  • 1
    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?2012-03-25

5 Answers 5

13

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

  • 0
    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?)2012-03-25
  • 1
    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$.)2012-03-25
  • 0
    Pretty obvious, don't know why I missed that. Thanks. (@anon, marlu updated his response after I replied)2012-03-25
  • 0
    @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.2012-03-25
  • 0
    @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?2012-03-25
  • 0
    @BillDubuque: When I had just posted my answer I read in a comment to your answer that the solution should be $2x^2+x+2$. I noticed that my solution could be further reduced and edited my answer. I am pretty sure that this did not take longer than 5 minutes.2012-03-25
  • 0
    @Bill and all: database updates sometimes take a while to propagate. It often takes a minute or more for tag edits or my other edits to bump a question to the front page (meaning, I edit something. Save. Go to the front page, and it won't be there until a few minutes later). I suspect this is similar here. If the server thinks marlu edited within the 5 minute window, then I see no reason (and no way) to dispute that here. To see the actual timing you'd have to contact the SE team, since it would require someone with raw DB/server log access.2012-03-26
  • 0
    I think 3rd line is wrong: (x+1) = (2x)*2 + 1. Did you mean (x+1) = (x/2)*2 + 1? Of course, the following solution is wrong too. The correct solution is (x^2-x+1)/2.2014-05-22
  • 0
    @miloszmaki: Remember that the polynomials have coefficients in $\mathbb F_3$, so that $4 = 1$ and $1/2 = 2$ and $-1 = 2$. Thus the solution you propose is actually the same as mine.2014-05-23
  • 0
    Oh, sorry. You're right. I haven't noticed that.2014-05-24
3

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.

  • 0
    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?2012-03-25
  • 1
    @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.2012-03-25
  • 0
    Understood, thanks.2012-03-25
  • 0
    [See here](https://math.stackexchange.com/a/637565/242) for another worked example.2017-07-01
2

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

  • 0
    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.2012-03-25
2

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.

-2

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
    Welcome to MathSE! Please see the site's LaTeX tutorial, which will help you to format your posts.2014-10-15
  • 1
    $x$ is an indeterminate. It is neither even nor odd. It has no "value". The congruences here are in the polynomial ring.2014-10-15