Math 361, Spring 2019, Assignment 15
From cartan.math.umb.edu
Solve the following problems:[edit]
- (Examples of cyclotomic polynomials):
- (a) Begin by choosing some concrete implementation of $GF(9)$, in which you know how to unambiguously write down elements, compare for equality, add, and multiply.
- (b) Show that every non-zero element of $GF(9)$ has multiplicative order either $1, 2, 4,$ or $8$. (Hint: what is the order of the group of units of $GF(9)$?)
- (c) For each $i\in\{1,2,4,8\}$, let $S_i$ denote the set of elements of $GF(9)$ whose multiplicative order is exactly $i$. Using your chosen implementation of $GF(9)$, list the elements of each $S_i$ explicitly.
- (d) For each $i\in\{1,2,4,8\}$, define $\Phi_i(x)=\prod_{a\in S_i}(x-a)$. Compute each polynomial $\Phi_i$ explicitly. Notice that although in principle the coefficients of $\Phi_i$ come from $GF(9)$, by an apparent coincidence they all land in $\mathbb{Z}_3$. The polynomial $\Phi_i$ is called the $i$th cyclotomic polynomial over $\mathbb{Z}_3$.
- (e) Compute the product $\Phi_1(x)\Phi_2(x)\Phi_4(x)\Phi_8(x)$. Does the result surprise you?
- (f) Try to generalize these results to $GF(p^n)$ for arbitrary $p,n$. Note that the result of (e) leads to a fairly fast recursive algorithm that computes $\Phi_i(x)$ even for moderately large $i$. The cyclotomic polynomials play a role in the theory of polynomial factorization over finite fields.
