Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section22.3Exercises

1

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)]\)

2

Calculate \([\gf(p^m): \gf(p^n)]\), where \(n \mid m\).

3

What is the lattice of subfields for \(\gf(p^{30})\)?

4

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)\).

5

Construct a finite field of order 27.

6

Prove or disprove: \({\mathbb Q}^\ast\) is cyclic.

7

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\)

8

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\).

9

Determine the number of cyclic codes of length \(n\) for \(n = 6\), 7, 8, 10.

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.

11

Construct all BCH codes of

  1. length 7.

  2. length 15.

12

Prove or disprove: There exists a finite field that is algebraically closed.

13

Let \(p\) be prime. Prove that the field of rational functions \({\mathbb Z}_p(x)\) is an infinite field of characteristic \(p\).

14

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\).

15

Show that every element in a finite field can be written as the sum of two squares.

16

Let \(E\) and \(F\) be subfields of a finite field \(K\). If \(E\) is isomorphic to \(F\), show that \(E=F\).

17

Let \(F \subset E \subset K\) be fields. If \(K\) is separable over \(F\), show that \(K\) is also separable over \(E\).

18

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.

19

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 )\).

20

Show that for every \(n\) there exists an irreducible polynomial of degree \(n\) in \({\mathbb Z}_p[x]\).

21

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\).

22

Show that every element in \(\gf(p^n)\) can be written in the form \(a^p\) for some unique \(a \in \gf(p^n)\).

23

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\)?

24Wilson's Theorem

Let \(p\) be prime. Prove that \((p-1)! \equiv -1 \pmod{p}\).

25

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\).

26

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.

27

Prove that the rings \(R_n\) and \({\mathbb Z}_2^n\) are isomorphic as vector spaces.

28

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]\).

29

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{equation*}G = \begin{pmatrix} g_0 & 0 & \cdots & 0 \\ g_1 & g_0 & \cdots & 0 \\ \vdots & \vdots &\ddots & \vdots \\ g_{n-k} & g_{n-k-1} & \cdots & g_0 \\ 0 & g_{n-k} & \cdots & g_{1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & g_{n-k} \end{pmatrix}\end{equation*} and \(H\) to be the \((n-k) \times n\) matrix \begin{equation*}H = \begin{pmatrix} 0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\ 0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ h_k & \cdots & h_0 & 0 & 0 & \cdots & 0 \end{pmatrix}.\end{equation*}

  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\).