1
$\begingroup$

$\mathbb Z_2[x]/\langle x^3+x^2+1\rangle $, I understand it is a field as $\langle x^3+x^2+1\rangle $ ideal is maximal ideal as the polynomial is irreducible over $Z_2$.

but I want to know how many elements are there in this field and how to find out that?

$\endgroup$
  • 2
    $\begingroup$ To work this out from first principles, the usual approach is to recognize that this field is a vector space over $\mathbb{Z}_2$. Finding a basis will help you determine how many elements there are! If you have trouble finding a basis, the simplest (IMO) observation is to try to work out an algorithm for simplifying an arbitrary polynomial to its simplest form modulo $x^3+x^2+1$. $\endgroup$ – user14972 Aug 18 '13 at 11:31
  • 1
    $\begingroup$ ??? I mention first principles, because the usual method to answer your question is to directly apply a formula involving the size of the base field and the degree of the irreducible polynomial. But the formula can be worked out by the approach I mention above. $\endgroup$ – user14972 Aug 18 '13 at 11:41
  • $\begingroup$ @Hurkyl thank you very much :) $\endgroup$ – miosaki Aug 18 '13 at 11:50
3
$\begingroup$

You have $x^3=x^2+1$ so you can eliminate powers of $x$ greater than $2$ and every element of the field is represented by a polynomial of order less than $3$.

Such polynomials have form $ax^2+bx+c$ and there are two choices in $\mathbb Z_2$ for each of $a,b,c$ so eight candidates. It remains to confirm that the eight elements are distinct (which is true because if two were equal we would get a factor of an irreducible polynomial).


Just to clarify, if we set $p(x)=x^3+x^2+1$ and we have any polynomial $f(x)$ we can use the division algorithm to write $f(x)=p(x)q(x)+r(x)$ where the degree of $r(x)$ is less than the degree of $p(x)$ - so $r(x)$ is a representative of the same element of the field as $f(x)$ - they differ by a multiple of $p(x)$. And $r(x)$ has degree at most 2. Which is what we need.

It is sometimes easier to compute $r(x)$ by using methods other than the division algorithm. An equivalent method is to treat $p(x)$ as if it is zero (since multiples of $p(x)$ count for nothing in the quotient field) (or simply $p(x)\equiv 0$ because it is in the same coset as zero). If we set $x^3+x^2+1\equiv 0$ and remember that twice anything is zero because our base field is $\mathbb Z_2$, we find that $x^3\equiv x^2+1$ - we can use this as an identity in the quotient field when we are doing explicit computations. The equivalence here is often written as an equality.

This second insight is one which will become familiar. In the quotient field, because we can treat $p(x)$ as if it is zero, we find that $x$ behaves as if it is a root of $p(x)$. So factoring by the ideals generated by irreducible polynomials is a way of creating new fields in which those polynomials have roots.

$\endgroup$
  • $\begingroup$ I dont understand why $x^3=x^2+1$ :( :( $\endgroup$ – miosaki Aug 18 '13 at 11:49
  • $\begingroup$ @miosaki: Mark Bennet is technically abusing notation in that expression. There, he uses $x$ to refer to the element $x+\langle x^3+x^2+1\rangle\in\mathbb Z_2[x]/\langle x^3+x^2+1\rangle$. It is a common abuse of notation though--I am certain I would have written $x$ instead of $\overline x$ or something. $\endgroup$ – user714630 Aug 18 '13 at 11:59
  • $\begingroup$ I am novice in higher mathematics, why mark bennet is answering like that from which I am not understanding a bit? :( $\endgroup$ – miosaki Aug 18 '13 at 12:03
  • $\begingroup$ @misosaki: I am trying to help, and perhaps have indicated a short cut. I will add something to my answer to clarify. $\endgroup$ – Mark Bennet Aug 18 '13 at 12:06
  • $\begingroup$ (+1) A relatively common practice is to define an auxiliary element $\alpha=x+\langle x^3+x^2+1\rangle$. Then $\alpha$ becomes a zero of the polynomial $x^3+x^2+1$ in the field $\mathbb{Z}_2[x]/\langle x^3+x^2+1\rangle$. This is a the usual way of creating a field, where a given irreducible polynomial has a zero. Vaguely related: in The second half o my answer to another question I give several examples of the arithmetic of the field $\mathbb{Z}_2[x]/\langle x^3+x^+1\rangle.$ The $\alpha$ there is different from the one above - it's just notaion. $\endgroup$ – Jyrki Lahtonen Aug 18 '13 at 20:10
5
$\begingroup$

Lemma 1

If $F$ is a field and if $p$ is an irreducible polynomial with coefficients in $F$, then $F[x]/(p)$ is a field.

Proof

A polynomial $p\in F[x]$ is irreducible if and only if $(p)$ is a maximal ideal in $F[x]$. A quotient $R/I$ of a commutative ring $R$ by an ideal $I$ is a field if and only if $I$ is a maximal ideal in $R$. Q.E.D.

Lemma 2

In the context of Lemma 1, $F\subseteq F[x]/(p)$ so $F[x]/(p)$ is a vector space over $F$. The dimension of this $F$-vector space is $\text{deg}(p)$.

Proof

Firstly, technically $F$ is not a subset of $F[x]/(p)$. However, the canonical homomorphism $F[x]\to F[x]/(p)$ restricts to a homomorphism of $F\to F[x]/(p)$ (since $F$ is a subset of $F[x]/(p)$). Furthermore, this map $F\to F[x]/(p)$ is injective (an element of $F[x]$ is sent to $0$ under $F[x]\to F[x]/(p)$ if and only if its divisible by $p$; clearly, no constant polynomial is divisible by $p$ except $0$). Therefore, we can view $F$ as a subset (in fact, a subfield) of $F[x]/(p)$.

We claim that the set ${\cal B}=\{1+(p),x+(p),x^2+(p),\dots,x^{\text{deg}(p)-1}+(p)\}$ is a basis for $F[x]/(p)$ as an $F$-vector space. Firstly, if $q+(p)\in F[x]/(p)$ (for $q\in F[x]$), then the division algorithm implies that $q=pa+b$ for $a,b\in F[x]$ and $b=0$ or $\text{deg}(b)<\text{deg}(p)$. Since $q+(p)=b+(p)$ and $b+(p)$ is clearly in the span of ${\cal B}$, it follows that ${\cal B}$ spans $F[x]/(p)$ as an $F$-vector space.

An equation of linear dependence for ${\cal B}$ is equivalent to a polynomial $q$ of degree less than that of $p$ equalling zero in $F[x]/(p)$. If the coefficients of $q$ were non-zero, then this would be a contradiction as $p$ cannot divide any non-zero polynomial of smaller degree. Therefore, $q=0$ and ${\cal B}$ is linearly independent.

Therefore, $F[x]/(p)$ is $\text{deg}(p)$-dimensional as an $F$-vector space. Q.E.D.

Lemma 3

If $V$ is a vector space of dimension $n$ over a finite field $F$ with $k$ elements, then $V$ has $k^n$ elements.

Proof

Exercise! Q.E.D.

Exercise: What is the number of elements in $\mathbb{Z}_2[x]/(x^3+x^2+1)$?

I hope this helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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