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.

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?

share|improve this question
add comment

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
+1 - very nice! I knew about Möbius invertion formula, but I never saw this particular application. –  Andrea Mori Apr 29 '12 at 21:49
add comment

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.

share|improve this answer
    
So you just enumerated all possible polynomials in $\mathbb{Z}_3$? Is there a better way to see this? –  rk101 Apr 29 '12 at 16:29
    
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. –  Andrea Mori Apr 29 '12 at 16:34
add comment

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.

share|improve this answer
    
No I can't, could you help explaining a little please? I understand that the finite field has $3^n$ elements, where $n$ is the deg of the minimum polynomial (of a primite element? which one?) - but here I am lost as to why this is the case. –  rk101 Apr 29 '12 at 16:27
    
Here's the way to think of it: by taking the quotient you are taking each polynomial and reducing it according to the rule $x^2\equiv -1$. So every polynomial would change into a polynomial of degree at most (how much?). –  rschwieb Apr 29 '12 at 16:30
    
Ah, so there are clearly $3$ cosets in the quotient, but why does each have order $3$? And you mean the rule $x^2 = -x$ –  rk101 Apr 29 '12 at 16:32
    
So the minimum polynomial of an element in the field $\mathbb{Z}_p$ has minimum polynomial of degree at most $(p-1)$, but does it have degree $(p-1)$ for every element? –  rk101 Apr 29 '12 at 16:35
    
There are 9 cosets. You did write $x^2+1$, so that would mean $x^2+1\equiv 0$ and so $x^2\equiv -1$. –  rschwieb Apr 29 '12 at 16:35
show 3 more comments

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.