Inverse of Polynomial

1. Nov 7, 2005

Icebreaker

Is there an algorithm for finding the inverse of a polynomial in Zp[x] where p is a prime?

2. Nov 7, 2005

AKG

Method of undetermined coefficients? Take a polynomial p(x), and for generality, express an undetermined polynomial q(x) as an infinite power series (although you know that all but finitely many of the coefficients will be 0), and you should be able to find an expression for the coefficient for xn in p(x)q(x) as some sum of terms made up of coefficients form p(x) and coefficients from q(x). You'll get that the coefficient of x0 in this product will of course be p(0)q(0), and you want this to be 1, so you can solve for the coefficient q(0). Next, you'll have some coefficient for x, and knowing the coefficients of p, and knowing q(0) (which is the coefficient of x0 in q(x)) you should be able to find another coefficient of q, since the coefficent of x in the product will have to equal 0. Continuing this process, you can determine the undetermined coefficients.

3. Nov 7, 2005

Icebreaker

This seems unlikely; I've seen this method in ODE but not in algebra. There must be something relating to the division algorithm in F[x].

4. Nov 7, 2005

AKG

The method of undetermined coefficients is just where you have undetermined coefficients and you determine them. It is a general idea. You can apply it to ODEs, but say you have a 2x2 matrix. Say you want to find its inverse. Multiply it by some general matrix with undetermined coefficients, and you'll get a bunch of linear equations for which you can solve for the undetermined coefficients and thereby find the inverse (if your original matrix was invertible). Suppose you have a power series f(x) and you want to find a power series g(x) such that f(x)g(x) = 1. Then you would do this by undetermined coefficients, i.e. g(x) is a power series with undetermined coefficients, then you can express f(x)g(x) as a power series with coefficients in terms of those of f and those of g, giving you a bunch of equations in which you can solve the undetermined coefficients.

Anyways, is Zp[x] even a field. I haven't studied much of this, but are you sure that elements have inverses? Suppose you have some polynomial q(x) of degree deg(q) with leading ceofficient aq. It's inverse would be some polynomial r(x) of degree deg(r) with leading coefficient ar. The product q(x)r(x) should be 1, so the coefficient of xdeg(q)+deg(r) ought to be 0, but it will be aqar which cannot be 0 if p is prime.

If this is right, then only polynomials of degree 0 have inverses. Or am I way off? Maybe I even have the multiplication wrong. When I've studied polynomial rings, the multiplication of polynomials has been p(x)q(x), but maybe you're studying something different where multiplication is composition, i.e. p(q(x)). In this case identity would be x, not 1, and the question of finding inverses gets more complicated, I think.

5. Nov 7, 2005

Icebreaker

I'm sorry, I did not post all hypotheses; I'm in the ring Z_2[x]/(x^3+x+1). I'll try to apply your method. Every element in this ring SHOULD be invertible due to a theorem that says if F is a field and p(x) is irreducible, then F[x]/p(x) is a field.

Every element of this ring/field is of the form ax^2+bx+c and a,b,c are either 0 or 1. I am currently brute-forcing it.

Last edited by a moderator: Nov 7, 2005
6. Nov 7, 2005

SN1987a

I brute-forced it too at first. In this particular case it turns out to be pretty easy: ring only has 7 elements. However, the method of undetermined coefficients works just as well, once again because this is a small ring and we don't have too many of them undetermined coefficients, so that it's not to hard to do the division algorithm.

7. Nov 7, 2005

Icebreaker

How odd that I've tried every element and still haven't found an inverse. Time for mathematica.

8. Nov 7, 2005

AKG

Finding the inverse of ax² + bx + c:

(ax²+bx+c)(dx²+ex+f)
= adx4 + (ae+bd)x³ + (af+eb+cd)x² + (bf+ec)x + cf
= [adx4 + (ae+bd)x³ + (af+eb+cd)x² + (be+ec)x + cf] - adx(x³+x+1)
= 1

cf-ae-bd = 1

You have 3 equations and 3 unknowns (d, e, and f), so you should be able to solve. This is the method of undetermined coefficients.

(c-a)d + be + af = 0
(-a-b)d + (b+c-a)e = 0
(-b)d + (-a)e + cf = 1

Since the field is Z2:

(c+a)d + (b)e + (a)f = 0
(a+b)d + (a+b+c)e = 0
(b)d + (a)e + (c)f = 1

Suppose a = b = c = 1. Then:

e + f = 0
e = 0
d + e + f = 1

The second equation gives e = 0. Combining that with the first gives f = 0. Combining those with the last gives d = 1, so the inverse of x² + x + 1 is x².

What exactly would you do with the division algorithm?

9. Nov 7, 2005

AKG

Also, you should be able to see right away that the inverse of x² + 1 is x, since:

(x² + 1)x = x³ + x = (x³ + x) - (x³ + x + 1) = -1 = 1

10. Nov 7, 2005

AKG

Actually, you know that x³ + x = 1, so maybe this is how you'd use the division algorithm? I.e. if you want to find the inverse of p(x), you'd divide x³+x by p(x) so that you'd get some q(x) such that x³+x = p(x)q(x) (and given that we have a field, you will be able to find such a q(x)) and then this q(x) would be your inverse?

11. Nov 7, 2005

Icebreaker

That's pretty much how I did it, yes. I'll keep this method of undetermined coefficients in my bag of tricks for later, though.

12. Nov 7, 2005

Hurkyl

Staff Emeritus
You could borrow tricks from modulo arithmetic (since that's essentially what this is): use GCDs to compute inverses! (The extended Euclidean algorithm, in particular)

If f(x) and p(x) are relatively prime, then there are polynomials u and v such that:
u(x) f(x) + v(x) p(x) = 1
and then u(x) is an inverse of f(x) modulo p(x)!

13. Nov 8, 2005

AKG

Nice. And so p(x) = x³+x+1 being irreducible is relatively prime to everything, in particular all the f(x) in our quotient field?

14. Nov 8, 2005

Hurkyl

Staff Emeritus
It sure is!