Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  Pierre-Yves Gaillard Mar 25 '12 at 16:20
add comment

4 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
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$.) –  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
show 4 more comments

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.

share|improve this answer
    
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
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. –  Bill Dubuque Mar 25 '12 at 16:50
    
Understood, thanks. –  David Chouinard Mar 25 '12 at 17:00
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.