2
$\begingroup$

I'm taking a class in finite fields and have not been able to conceptualize how modulo + finite fields works in polynomial space. I understand the basic premises of modular arithmetic, but can't work out how to actually generate a finite field of polynomials.

For example:

Find all $f(x)$ and $g(x)$ in $\mathbb Z_3[x]$: $$(x^3 + x +1) f(x) + (x^2 + x +1)g(x) = 1$$

I know conceptually how to solve this sort of equation when the coefficients are integers and $f(x), g(x)$ are simple variables, but I don't know how to generate fields in $\mathbb Z_3[x]$ and then how exactly to use them to solve this sort of equation for polynomials once I have their $\mathrm{gcd}$ in $\mathbb Z_3[x]$.

  • 0
    Do you know how to do long division on $$\frac{x^3 + x +1}{x^2 + x +1}$$ in ${\mathbb Z}_3[x]$? i.e. compute quotient and remainder? That's what you need to compute the Extended Euclidean algorithm for polynomials. For example, [these pdf notes](http://www.math.ucdavis.edu/~deloera/TEACHING/MATH165/extendedeuclid.pdf)2012-03-29
  • 0
    @J.D. I understand how to do polynomial long division, but am kind of confused on how it differs when in $\mathbb Z_3[x]$2012-03-29
  • 0
    @Stephen Young: Almost like the usual, except that the arithmetic on the coefficients goes modulo $3$. So $x^2+x+1$ "goes into $x^3+x+1$" $x$ times. Multiply, you get $x^3+x^2+x$. Subtract from $x^3+x+1$. We get (x^3+x+1)-(x^3+x^2+x)=-x^2+1=2x^2+1$. Continue.2012-03-29
  • 0
    Thanks @AndréNicolas - so is the $\mathbb Z_3[x]$ just referring to the modulo of the coefficients then? I'm trying to wrap my head around how to generate a finite field from a statement like $\mathbb Z_3[x]$ / m(x)2012-03-29
  • 0
    Yes, your definition of $\mathbb{Z}_3[x]$ is exactly right. Now if we have a polynomial irreducible over $\mathbb{Z}_3$, like $x^2+1$, we can look at $\mathbb{Z}_3[x]/(x^2+1)$, which means we think of polynomials as being "equivalent" if they differ by a multiple of $x^2+1$. It turns out that any polynomial is equivalent to $a+bx$, where $a$, $b$ range independently over $\mathbb{Z}_3$. So $9$ elements, and they form a field.2012-03-29
  • 0
    Polynomial arithmetic in $\mathbb Z_3[x]/(m(x))$ is polynomial arithmetic in $\mathbb Z[x]$ with results reduced $\bmod{m(x)}$ and coefficients reduced $\bmod{3}.$2012-03-29
  • 0
    André already told you that in the example case there are no solutions. Another way of seeing this is to observe that in the ring $\mathbb{Z}_3[x]$ we have $$x^2+x+1=x^2-2x+1=(x-1)^2,$$ and $$x^3+x+1=(x^3-x^2)+(x^2+x+1)=(x-1)x^2+(x-1)^2=(x-1)(x^2+x-1).$$2012-03-29
  • 1
    Thanks everyone, really helpful stuff - learned more tonight than in the last two months of lectures.2012-03-29

1 Answers 1