Exercises22.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)]$$

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

5.

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

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

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

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

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

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.

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

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