## Exercises17.4Exercises

###### 1.

Calculate each of the following.

1. $\displaystyle [\gf(3^6) : \gf(3^3)]$

2. $\displaystyle [\gf(128): \gf(16)]$

3. $\displaystyle [\gf(625) : \gf(25) ]$

4. $\displaystyle [\gf(p^{12}): \gf(p^2)]$

Hint

Make sure that you have a field extension.

###### 2.

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

###### 3.

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

###### 4.

Let $\alpha$ be a zero of $x^3 + x^2 + 1$ over ${\mathbb Z}_2\text{.}$ Construct a finite field of order $8\text{.}$ Show that $x^3 + x^2 + 1$ splits in ${\mathbb Z}_2(\alpha)\text{.}$

Hint

There are eight elements in ${\mathbb Z}_2(\alpha)\text{.}$ Exhibit two more zeros of $x^3 + x^2 + 1$ other than $\alpha$ in these eight elements.

###### 5.

Construct a finite field of order $27\text{.}$

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.

###### 6.

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

###### 7.

Factor each of the following polynomials in ${\mathbb Z}_2[x]\text{.}$

1. $\displaystyle x^5- 1$

2. $\displaystyle x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$

3. $\displaystyle x^9 - 1$

4. $\displaystyle x^4 +x^3 + x^2 + x + 1$

Hint

(a) $x^5 -1 = (x+1)(x^4+x^3 + x^2 + x+ 1)\text{;}$ (c) $x^9 -1 = (x+1)( x^2 + x+ 1)(x^6+x^3+1)\text{.}$

###### 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\text{.}$

Hint

True.

###### 9.

Determine the number of cyclic codes of length $n$ for $n = 6, 7, 8, 10\text{.}$

###### 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\text{.}$

2. length $15\text{.}$

Hint

(a) Use the fact that $x^7 - 1 = (x + 1)( x^3 + x + 1)(x^3 + x^2 + 1)\text{.}$

###### 12.

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

Hint

False.

###### 13.

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

###### 14.

Let $D$ be an integral domain of characteristic $p\text{.}$ Prove that $(a - b)^{p^n} = a^{p^n} - b^{p^n}$ for all $a, b \in D\text{.}$

###### 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\text{.}$ If $E$ is isomorphic to $F\text{,}$ show that $E = F\text{.}$

###### 17.

Let $F \subset E \subset K$ be fields. If $K$ is a separable extension of $F\text{,}$ show that $K$ is also separable extension of $E\text{.}$

Hint

If $p(x) \in F[x]\text{,}$ then $p(x) \in E[x]\text{.}$

###### 18.

Let $E$ be an extension of a finite field $F\text{,}$ where $F$ has $q$ elements. Let $\alpha \in E$ be algebraic over $F$ of degree $n\text{.}$ Prove that $F( \alpha )$ has $q^n$ elements.

Hint

Since $\alpha$ is algebraic over $F$ of degree $n\text{,}$ 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\text{.}$ There are $q^n$ possible $n$-tuples $(a_0, a_1, \ldots, a_{n - 1})\text{.}$

###### 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\text{,}$ prove that there exists an $\alpha \in E$ such that $E = F( \alpha )\text{.}$

###### 20.

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

###### 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\text{.}$

###### 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)\text{.}$

###### 23.

Let $E$ and $F$ be subfields of $\gf(p^n)\text{.}$ If $|E| = p^r$ and $|F| = p^s\text{,}$ what is the order of $E \cap F\text{?}$

###### 24.Wilson's Theorem.

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

Hint

Factor $x^{p-1} - 1$ over ${\mathbb Z}_p\text{.}$

###### 25.

If $g(t)$ is the minimal generator polynomial for a cyclic code $C$ in $R_n\text{,}$ prove that the constant term of $g(x)$ is $1\text{.}$

###### 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)\text{.}$ If $\langle f(t) \rangle$ is another code in $R_n\text{,}$ 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]\text{.}$

###### 29.

Let $C = \langle g(t) \rangle$ be a cyclic code in $R_n$ and suppose that $x^n - 1 = g(x) h(x)\text{,}$ 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\text{.}$ 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}\text{.} \end{equation*}
1. Prove that $G$ is a generator matrix for $C\text{.}$

2. Prove that $H$ is a parity-check matrix for $C\text{.}$

3. Show that $HG = 0\text{.}$