3
$\begingroup$

Let $K = GF(3^2)$. Then $K \cong \frac{\mathbb{Z}_3[x]}{(x^2 + 1)} $.

But Why? Also I understand why $x^2 + 1$ is irreducible in $\mathbb{Z}_3$, but not how to get other irreducible polynomials of degree 2 in $\mathbb{Z}_3$.

Can anybody please help?

4 Answers 4

0

Hint: Since there is only a unique (up to isomorphism) finite field of any given order, it would be enough to see that $(x^2+1)$ is a maximal ideal, and that the quotient ring only has 9 elements.

Can you see that the quotient has 9 elements?

Can you see the connection between the polynomial being maximal and the polynomial being irreducible?

Another hint about your second question: a reducible second (or third) degree polynomial over a field is going to have to have a root in the field.

  • 0
    You have $\alpha x+\beta$ for any $\alpha,\beta$ in the field of three elements. A polynomial with higher degree will be reduced to one with degree 1 or less by your degree 2 relation. Since there are a total of 9 distinct choices of pairs of coefficients, you have nine things in the residue.2012-04-29
6

To contribute a very partial answer to the second question of how to get the other irreducibles, let me point out that you have a way of knowing how many irreducibles of each degree there are. It makes use of the Möbius Inversion Formula, which I think everyone should know, but which I’m ashamed to say I didn’t learn till long after I left graduate school. It says that if $f$ and $g$ are two functions defined on the positive integers, related by the formula $f(n)=\sum_{d|n}g(d)$, then they are also related by the “inverted” formula $g(n)=\sum_{d|n}\mu(n/d)f(d)$. This makes use of the “Möbius function” $\mu$, also defined for positive integers only, for which $\mu(n)=0$ if $n$ is divisible by a square bigger than $1$, but otherwise $\mu(n)=(-1)^s$ if $n$ is divisible by $s$ different primes.

From a close investigation of the polynomial $X^{p^n}-X$ over the field with $p$ elements, you discover that if you call $M(n)$ the number of monic irreducible polynomials of degree $n$ over ${\mathbb{F}}_p$, then $ p^n = \sum_{d|n}dM(d)\,, $ so you apply MIF to this and find that $M(n)=(1/n)\sum_{d|n}\mu(n/d)p^d$.

For instance, applying this to $p=3$, you get $M(2)=(9-3)/2=3$, so the three that have been mentioned earlier are the only ones. Similarly, $M(3)=(27-3)/3=8$, and you may have fun trying to write out all eight irreducible cubics over ${\mathbb{F}}_3$.

  • 0
    +1 - very nice! I knew about Möbius invertion formula, but I never saw this particular application.2012-04-29
5

GF$(3^2)$ can be constructed from GF$(3)$ is exactly the same way as $\mathbb C$ is constructed from $\mathbb R$ when complex numbers are first introduced to beginning students of mathematics. Just as the polynomial $x^2 + 1 \in \mathbb R[x]$ has no roots in $\mathbb R$, the polynomial $x^2 + 1 \in$ GF$(3)[x]$ has no roots in GF$(3)$. In both cases, one adjoins an element $i = \sqrt{-1}$ --- a root of the polynomial $x^2 + 1$ --- to the base field, and then creates new elements by the field operations of addition and multiplication applied to the adjoined element $i$. The properties of commutativity and associativity of addition and multiplication as well as the distributivity of multiplication over addition are assumed to hold in the field thus extended. In the case of $\mathbb R$, these operations lead to the creation of elements of the form $a + bi ~ a, b \in \mathbb R$ resulting in the complex field $\mathbb C$. Higher powers of $i$ are not necessary since $i^2 = -1 \in \mathbb R$ and thus any $i^n$ can be reduced to an element of the set $\{+1, -1, +i, -i\}$. Similarly, adjoining $i$ to GF$(3)$ gives the field GF$(3^2)$ whose nine elements are of the form $a + bi, ~ a, b \in \text{GF}(3)$. Note that $(3-a) + (3-b)i = -a -bi$ is the (unique) additive inverse of $a + bi$. Just as $a + bi \in \mathbb C$ has (unique) multiplicative inverse $(a - bi)/(a^2 + b^2) \in \mathbb C$, the (unique) multiplicative inverse of $a + bi \in \text{GF}(3^2)$ is $(a - bi)/(a^2 + b^2)$. Note that $a/(a^2 + b^2)$ and $-b/(a^2 + b^2) = 2b/(a^2 + b^2)$ are elements of GF$(3)$. In this formulation, each element of GF$(3^2)$ (or of $\mathbb C$) is described as a polynomial (of degree less than $2$) in the adjoined element $i$ which is a root of a polynomial of degree $2$.

It is also possible to consider the elements of $\mathbb C$ as polynomials of degree $1$ in an indeterminate $x$. The field operations in $\mathbb C$ then are polynomial addition and multiplication modulo $x^2 + 1$. Similarly, it is possible to consider the elements of GF$(3^2)$ as polynomials of degree $1$ in an indeterminate $x$ with field operations being polynomial addition and multiplication modulo $x^2 + 1$. In this latter case, remember that the coefficients of the polynomials are being added or multiplied modulo $3$. In either field, whether one computes $\begin{align*} (a + bx)(c + dx) &= ac + (bc + ad)x + bdx^2\\ &= (ac - bd) + (bc + ad)x + bd(x^2 + 1)\\ &\equiv (ac - bd) + (bc + ad)x \bmod (x^2 + 1)\\ \end{align*}$ or one computes $\begin{align*} (a + bi)(c + di) &= ac + (bc + ad)i + bdi^2\\ &= ac + (bc + ad)i - bd\\ &= (ac - bd) + (bc + ad)i \end{align*}$ is perhaps a matter of taste, but beginning students of finite fields are often confused when they see the field regarded sometimes as polynomials in an indeterminate and sometimes as polynomials in an element of the extension field.

Turning to the question of finding other irreducible polynomials, just as $a+bi$ and $a-bi$ are conjugates in $\mathbb C$, meaning that both are roots of the same monic polynomial $x^2 - 2ax + (a^2+b^2) \in \mathbb R[x]$, $a+bi$ and $a-bi$ are conjugates in GF$(3^2)$, meaning that both are roots of the same monic quadratic polynomial $x^2 - 2ax + (a^2+b^2) = x^2 + ax + (a^2+b^2) \in \text{GF}(3)[x].$ The choices $a=b=0$ and $a=\pm 1, b=0$ are elements of GF$(3)$ and the quadratic polynomials are reducible, while choices $a=0, b=\pm 1$, $a=1, b=\pm 1$, and $a=2, b=\pm 1$ give the three irreducible polynomials listed by Andrea Mori and also helps you easily identify which element of GF$(3^2)$ is a root of which polynomial.

4

A polynomial of degree $\leq3$ over any field $K$ is irreducible if and only if it has no roots in $K$.

Now in $\Bbb F_3$:

  • $x^2+2$ has roots $\pm1$,

  • $x^2+x+1$ has root $1$,

  • $x^2+x+2$ has no roots, so it is irreducible,

  • $x^2+2x+1$ has root $2$,

  • $x^2+2x+2$ has no roots, so it is irreducible,

  • any polynomial with zero constant term has root $0$.

Thus we have obtained a complete list of irreducible polynomials of degree 2.

  • 0
    If you want to construct an explicit irreducible polynomial of low degree over a field with few elements, enumerating the polynomials may be the quickest route. Mind that, as I said, the root check works only in degree $\leq3$, but you can still enumerate *reducible* polynomials of higher degree by multiplying together polynomials of smaller degree. The observation that it is enough to consider monic polynomials makes a bit of a shortcut.2012-04-29