maths.free › Abstract Algebra › 22. Finite Fields › Finite Fields: exercises

Finite Fields: exercises

Finite Fields: exercises — from Judson, Abstract Algebra: Theory and Applications.

Practice (33)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Calculate each of the following.
1. \([\gf(3^6) : \gf(3^3)]\)
2. \([\gf(128): \gf(16)]\)
3. \([\gf(625) : \gf(25) ]\)
4. \([\gf(p^{12}): \gf(p^2)]\)
גלה את התשובה

Hint:
Make sure that you have a field extension.
Calculate \([\gf(p^m): \gf(p^n)]\), where \(n \mid m\).
What is the lattice of subfields for \(\gf(p^{30})\)?
Let \(\alpha\) be a zero of \(x^3 + x^2 + 1\) over \({\mathbb Z}_2\). Construct a finite field of order \(8\). Show that \(x^3 + x^2 + 1\) splits in \({\mathbb Z}_2(\alpha)\).

גלה את התשובה

Hint:
There are eight elements in \({\mathbb Z}_2(\alpha)\). Exhibit two more zeros of \(x^3 + x^2 + 1\) other than \(\alpha\) in these eight elements.
Construct a finite field of order \(27\).

גלה את התשובה

Hint:
Find an irreducible polynomial \(p(x)\) in \({\mathbb Z}_3[x]\) of degree \(3\) and show that \({\mathbb Z}_3[x]/ \langle p(x) \rangle\) has \(27\) elements.
Prove or disprove: \({\mathbb Q}^\ast\) is cyclic.
Factor each of the following polynomials in \({\mathbb Z}_2[x]\).
1. \(x^5- 1\)
2. \(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\)
3. \(x^9 - 1\)
4. \(x^4 +x^3 + x^2 + x + 1\)
גלה את התשובה

Hint:
(a) \(x^5 -1 = (x+1)(x^4+x^3 + x^2 + x+ 1)\); (c) \(x^9 -1 = (x+1)( x^2 + x+ 1)(x^6+x^3+1)\).
Prove or disprove: \({\mathbb Z}_2[x] / \langle x^3 + x + 1 \rangle \cong {\mathbb Z}_2[x] / \langle x^3 + x^2 + 1 \rangle\).

גלה את התשובה

Hint:
True.
Determine the number of cyclic codes of length \(n\) for \(n = 6, 7, 8, 10\).
Prove that the ideal \(\langle t + 1 \rangle\) in \(R_n\) is the code in \({\mathbb Z}_2^n\) consisting of all words of even parity.
Construct all BCH codes of
1. length \(7\).
2. length \(15\).
גלה את התשובה

Hint:
(a) Use the fact that \(x^7 - 1 = (x + 1)( x^3 + x + 1)(x^3 + x^2 + 1)\).
Prove or disprove: There exists a finite field that is algebraically closed.

גלה את התשובה

Hint:
False.
Let \(p\) be prime. Prove that the field of rational functions \({\mathbb Z}_p(x)\) is an infinite field of characteristic \(p\).
Let \(D\) be an integral domain of characteristic \(p\). Prove that \((a - b)^{p^n} = a^{p^n} - b^{p^n}\) for all \(a, b \in D\).
Show that every element in a finite field can be written as the sum of two squares.
Let \(E\) and \(F\) be subfields of a finite field \(K\). If \(E\) is isomorphic to \(F\), show that \(E = F\).
Let \(F \subset E \subset K\) be fields. If \(K\) is a separable extension of \(F\), show that \(K\) is also separable extension of \(E\).

גלה את התשובה

Hint:
If \(p(x) \in F[x]\), then \(p(x) \in E[x]\).
Let \(E\) be an extension of a finite field \(F\), where \(F\) has \(q\) elements. Let \(\alpha \in E\) be algebraic over \(F\) of degree \(n\). Prove that \(F( \alpha )\) has \(q^n\) elements.

גלה את התשובה

Hint:
Since \(\alpha\) is algebraic over \(F\) of degree \(n\), we can write any element \(\beta \in F(\alpha)\) uniquely as \(\beta = a_0 + a_1 \alpha + \cdots + a_{n - 1} \alpha^{n - 1}\) with \(a_i \in F\). There are \(q^n\) possible \(n\)-tuples \((a_0, a_1, \ldots, a_{n - 1})\).
Show that every finite extension of a finite field \(F\) is simple; that is, if \(E\) is a finite extension of a finite field \(F\), prove that there exists an \(\alpha \in E\) such that \(E = F( \alpha )\).
Show that for every \(n\) there exists an irreducible polynomial of degree \(n\) in \({\mathbb Z}_p[x]\).
Prove that the Frobenius map \(\Phi : \gf(p^n) \rightarrow \gf(p^n)\) given by \(\Phi : \alpha \mapsto \alpha^p\) is an automorphism of order \(n\).
Show that every element in \(\gf(p^n)\) can be written in the form \(a^p\) for some unique \(a \in \gf(p^n)\).
Let \(E\) and \(F\) be subfields of \(\gf(p^n)\). If \(|E| = p^r\) and \(|F| = p^s\), what is the order of \(E \cap F\)?
Let \(p\) be prime. Prove that \((p-1)! \equiv -1 \pmod{p}\).

גלה את התשובה

Hint:
Factor \(x^{p-1} - 1\) over \({\mathbb Z}_p\).
If \(g(t)\) is the minimal generator polynomial for a cyclic code \(C\) in \(R_n\), prove that the constant term of \(g(x)\) is \(1\).
Often it is conceivable that a burst of errors might occur during transmission, as in the case of a power surge. Such a momentary burst of interference might alter several consecutive bits in a codeword. Cyclic codes permit the detection of such error bursts. Let \(C\) be an \((n,k)\)-cyclic code. Prove that any error burst up to \(n-k\) digits can be detected.
Prove that the rings \(R_n\) and \({\mathbb Z}_2^n\) are isomorphic as vector spaces.
Let \(C\) be a code in \(R_n\) that is generated by \(g(t)\). If \(\langle f(t) \rangle\) is another code in \(R_n\), show that \(\langle g(t) \rangle \subset \langle f(t) \rangle\) if and only if \(f(x)\) divides \(g(x)\) in \({\mathbb Z}_2[x]\).
Let \(C = \langle g(t) \rangle\) be a cyclic code in \(R_n\) and suppose that \(x^n - 1 = g(x) h(x)\), where \(g(x) = g_0 + g_1 x + \cdots + g_{n - k} x^{n - k}\) and \(h(x) = h_0 + h_1 x + \cdots + h_k x^k\). Define \(G\) to be the \(n \times k\) matrix \[\begin{aligned}\end{aligned}\] and \(H\) to be the \((n-k) \times n\) matrix \[\begin{aligned}\end{aligned}\].
1. Prove that \(G\) is a generator matrix for \(C\).
2. Prove that \(H\) is a parity-check matrix for \(C\).
3. Show that \(HG = 0\).
Show that \(w(t)\) is a code polynomial if and only if \(s_i = 0\) for all \(i\).
Show that \[\begin{aligned}\end{aligned}\] for \(i = 1, \ldots, 2r\). The error-locator polynomial is defined to be \[\begin{aligned}\end{aligned}\].
Recall the \((15,7)\)-block BCH code in . By , this code is capable of correcting two errors. Suppose that these errors occur in bits \(a_1\) and \(a_2\). The error-locator polynomial is \(s(x) = (x + \omega^{a_1})(x + \omega^{a_2})\). Show that \[\begin{aligned}\end{aligned}\].
Let \(w(t) = 1 + t^2 +t^4 + t^5 + t^7 + t^{12} + t^{13}\). Determine what the originally transmitted code polynomial was.

Symbols used here

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

נסה את שלך.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

יותר בפנים. Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula