## Category Archives: AA:DF

### The order of the Frobenius map on a finite field

Let $\varphi$ denote the Frobenius map $x \mapsto x^p$ on $\mathbb{F}_{p^n}$. Prove that $\varphi$ is an automorphism and compute its order in $\mathsf{Aut}(\mathbb{F}_{p^n})$.

Recall that $\varphi$ is a homomorphism. Moreover, if $\alpha \in \mathsf{ker}\ \varphi$, then $\alpha^p = 0$. Since fields contain no nontrivial zero divisors, we have $\alpha = 0$ (using induction if you want). So the kernel of $\varphi$ is trivial, and thus $\varphi$ is injective. Since $\mathbb{F}_{p^n}$ is finite, $\varphi$ is surjective, and so is a field isomorphism.

Next, we claim that $\varphi^t(\alpha) = \alpha^{p^t}$ for all $\alpha$ and all $t \geq 1$, and will show this by induction. The base case certainly holds, and if $\varphi^t(\alpha) = \alpha^{p^t}$, then $\varphi^{t+1}(\alpha) = \varphi(\varphi^t(\alpha)) = \varphi(\alpha^{p^t})$ $= (\alpha^{p^t})^p$ $= \alpha^{p^{t+1}}$ as desired.

Now $\varphi^n(\alpha) = \alpha^{p^n} = \alpha$, since the elements of $\mathbb{F}_{p^n}$ are precisely the roots of $x^{p^n}-x$. So we have $\varphi^n = 1$.

If $\varphi^t = 1$, then we have $\alpha^{p^t} - \alpha = 0$ for all $\alpha$, so that each $\alpha$ is a root of $x^{p^t}-x$. So $x^{p^n-1}-1$ divides $x^{p^t-1}-1$, and so $p^n-1$ divides $p^t-1$ (by this previous exercise) and then $n$ divides $t$ (by this previous exercise). In particular, $n \leq t$.

So $n$ is the order of $\varphi$ in $\mathsf{Aut}(\mathbb{F}_{p^n})$.

### Over CC, matrices of finite multiplicative order are diagonalizable

Let $A$ be an $n \times n$ matrix over $\mathbb{C}$. Show that if $A^k=I$ for some $k$, then $A$ is diagonalizable.

Let $F$ be a field of characteristic $p$. Show that $A = \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix}$ has finite order but cannot be diagonalized over $F$ unless $\alpha = 0$.

Since $A^k = I$, the minimal polynomial $m$ of $A$ over $\mathbb{C}$ divides $x^k-1$. In particular, the roots of $m$ are distinct. Since $\mathbb{C}$ contains all the roots of unity, by Corollary 25 on page 494 of D&F, $A$ is diagonalizable over $\mathbb{C}$.

Note that $\begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & \beta \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & \alpha+\beta \\ 0 & 1 \end{bmatrix}$. By an easy inductive argument, then, $\begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix}^t = \begin{bmatrix} 1 & t\alpha \\ 0 & 1 \end{bmatrix}$, and in particular, $A^p = I$.

Suppose $\alpha \neq 0$. Now $\frac{1}{\alpha}A$ is in Jordan canonical form, and is not diagonalizable. (See Corollary 24 on page 493 of D&F.) So $A$ cannot be diagonalizable, for if it were, then so would $\frac{1}{\alpha}A$. (If $P^{-1}AP = D$ is diagonal, then so is $P^{-1}\frac{1}{\alpha}AP = \frac{1}{\alpha}D$.)

### On the factors of a cyclotomic polynomial over ZZ/(p)

Let $\ell$ be a prime and let $\Phi_\ell(x) = \frac{x^\ell-1}{x-1} \in \mathbb{Z}[x]$ be the $\ell$th cyclotomic polynomial. (Remember that $\Phi_\ell$ is irreducible over $\mathbb{Z}$.) Let $p$ be a prime and let $\zeta$ denote any fixed primitive $\ell$th root of unity.

1. Show that if $p=\ell$ then $\Phi_\ell(x) = (x-1)^{\ell-1} \in \mathbb{F}_p[x]$.
2. Suppose $p \neq \ell$ and let $f$ denote the order of $p$ in $\mathbb{F}_\ell$. (That is, $f$ is minimal such that $p^f \equiv 1$ mod $\ell$.) Show that $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$. Conclude that the minimal polynomial of $\zeta$ over $\mathbb{F}_p$ has degree $f$.
3. Show that $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ for any integer $a$ not divisible by $\ell$. Conclude that, in $\mathbb{F}_p[x]$, $\Phi_\ell(x)$ is the product of $\frac{\ell-1}{f}$ distinct irreducible polynomials of degree $f$.
4. As an example, find the degrees of the irreducible factors of $\Phi_7(x)$ over $\mathbb{F}_p$.

1. Mod $p=\ell$, we have $x^\ell-1 = (x-1)^\ell$. So $\Phi_\ell(x) = (x-1)^{\ell-1}$ as desired.
2. Note that $\zeta \in \mathbb{F}_{p^f}$ precisely when $\zeta$ is a root of $x^{p^f-1}-1$. Since $p^f \equiv 1$ mod $\ell$, we have that $\ell$ divides $p^f-1$. By this previous exercise, $x^\ell - 1$ divides $x^{p^f-1}-1$. Since $\zeta$ is a $\ell$th root of unity, $\zeta \in \mathbb{F}_{p^f}$. Conversely, suppose $\zeta \in \mathbb{F}_{p^t}$. Now $\zeta^\ell \equiv 1$, so $\ell$ divides $p^t-1$ by Lagrange’s theorem in the group $\mathbb{F}_{p^t}^\times$. Thus $p^t \equiv 1$ mod $\ell$, and so $f$ divides $t$. So $f$ is minimal such that $\zeta \in \mathbb{F}_{p^f}$.

Next we claim that $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^f}$. The $(\subseteq)$ inclusion is clear since $\zeta \in \mathbb{F}_{p^f}$. $(\supseteq)$ $\mathbb{F}_p(\zeta) = \mathbb{F}_{p^t}$ for some $t$, since finite fields are essentially unique. By the preceding argument, $f|t$, so $\mathbb{F}_{p^f} \subseteq \mathbb{F}_{p^t} = \mathbb{F}_p(\zeta)$ using this previous exercise.

3. It is clear that $\mathbb{F}_p(\zeta^a) \subseteq \mathbb{F}_p(\zeta)$. Conversely, since $\ell$ does not divide a\$, by Bezout’s identity there exist $x,y \in \mathbb{Z}$ such that $ax + \ell y = 1$. Now $(\zeta^a)^x = \zeta^{ax}$ $= \zeta^{1-\ell y}$ $= \zeta$. So $\mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a)$ provided $\ell$ does not divides $a$.

Now consider $\Phi_\ell(x)$ as a polynomial over $\mathbb{F}_p$. Let $\zeta_i$ be the distinct primitive $\ell$th roots of unity. By part (b), $\mathbb{F}_p(\zeta_i)$ has degree $f$ over $\mathbb{F}_p$ for each $i$, so the minimal polynomial of $\zeta_i$ over $\mathbb{F}_p$ has degree $f$. So the irreducible factors of $\Phi_\ell$ have degree $f$, and there are $\frac{\ell-1}{f}$ such factors. Moreover, since $\Phi_\ell$ is separable, its factors are distinct.

4. If $p \equiv 1$ mod 7, then $\Phi_7(x) = (x-1)^6$ by part (a). Evidently 2 and 4 have order 3 mod 7, so if $p \in \{2,4\}$ mod 7 then $\Phi_7(x)$ factors into two irreducible cubics. Similarly, 3 and 5 have order 6 mod 7, so that if $p \in \{3,5\}$ mod 7 then $\Phi_7(x)$ is irreducible. Since 6 has order 2 mod 7, if $p \equiv 6$ mod 7, then $\Phi_7(x)$ factors into three irreducible quadratics.

### An alternate characterization of cyclotomic polynomials

Prove that $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$, where $\Phi_n$ is the $n$th cyclotomic polynomial and $\mu$ is the Möbius function on $\mathbb{N}^+$ defined by $\mu(1) = 1$, $\mu(m) = (-1)^r$ if $m$ is squarefree with $r$ distinct prime factors, and $\mu(m) = 0$ if $m$ is divisible by a square.

[I consulted this document from the Berkeley Math Circle when preparing this solution.]

Before we approach this (seemingly magical) identity, let’s build up some machinery.

Given an abelian group $A$, let $A_0^\mathbb{N}$ denote the set of all functions $\mathbb{N}^+ \rightarrow A$. Recall that $A^\mathbb{N}_0$ is itself an abelian group under pointwise addition.

Now let $R$ be a commutative ring with 1 and let $M$ be a left $R$-module. Define an operator $R_0^\mathbb{N} \times M_0^\mathbb{N} \rightarrow M_0^\mathbb{N}$ by $(f \ast_{R,M} g)(n) = \sum_{st=n} f(s) g(t)$. Note that since $n$ is positive, this sum is finite, and that $s$ and $t$ are nonzero. We will usually drop the subscripts on $\ast$. This operator is called the Dirichlet convolution of $f$ and $g$.

Lemma 1: Let $f,g \in R^\mathbb{N}_0$ and $h \in M^\mathbb{N}_0$. Then $f \ast_{R,M} (g \ast_{R,M} h) = (f \ast_{R,R} g) \ast_{R,M} h$. Proof: We have

 $(f \ast (g \ast h))(n)$ = $\sum_{st=n} f(s)(g \ast h)(t)$ = $\sum_{st=n} f(s) \sum_{uv=t} g(u)h(v)$ = $\sum_{st=n} \sum_{uv=t} f(s)g(u)h(v)$ = $\sum_{suv=n} f(s)g(u)h(v)$ = $\sum_{tv=n} \sum_{su=t} f(s)g(u)h(v)$ = $\sum_{tv=n} (\sum_{su=t} f(s)g(u)) h(v)$ = $\sum_{tv=n} (f \ast g)(t)h(v)$ = $((f \ast g) \ast h)(n)$

As desired. $\square$

Lemma 2: Let $f,g \in R^\mathbb{N}_0$ and $h,k \in M^\mathbb{N}_0$. Then (using pointwise addition) we have $(f+g) \ast h = (f \ast h) + (g \ast h)$ and $f \ast (h + k) = (f \ast h) + (f \ast k)$. Proof: We have

 $(f \ast (h+k))(n)$ = $\sum_{st=n} f(s)(h+k)(t)$ = $\sum_{st=n} f(s)(h(t)+k(t))$ = $\sum_{st=n} f(s)h(t) + \sum_{st=n} f(s)k(t)$ = $(f \ast h)(n) + (f \ast k)(n)$ = $((f \ast h) + (f \ast k))(n)$

as desired. The other equality is analogous. $\square$

Corollary 1: $R^\mathbb{N}_0$ is a ring with pointwise addition and Dirichlet convolution, and $M^\mathbb{N}_0$ is a left $R^\mathbb{N}_0$ module via Dirichlet convolution. Proof: Follows from Lemmas 1 and 2. $\square$

Let $\delta_{1,n}$ denote the Kronecker delta (whose value is 1 if $n=1$ and 0 otherwise) and let $\mu : \mathbb{N}^+ \rightarrow R$ be the Möbius function.

Lemma 3: For all $g \in R^\mathbb{N}+0$, $\delta_{1,n} \ast g = g$. Proof: We have $(\delta_{1,n} \ast g)(n) = \sum_{st=n} \delta_{1,s}g(t)$. Now the delta function is 0 unless $s = 1$, in which case $t = n$, and so this sum is precisely $g(n)$ as desired. $\square$

Now let $1$ denote the constant function whose value is 1.

Lemma 4: $\mu \ast 1 = \delta_{1,n}$. Proof: We have $(\mu \ast 1)(n) = \sum_{st=n} \mu(s)1(t)$ $= \sum_{s|n} \mu(s)$. If $n = 1$, then we have $(\mu \ast 1)(1) = \delta_{1,1}$. Now suppose $n = p_1^{e_1} \cdots p_k^{e_k}$, with the $p_i$ prime. Now $s = p_1^{d_1} \cdots p_k^{d_k}$, where $0 \leq d_i \leq e_i$. Note that if any $d_i$ is greater than 1, then (by definition) $\mu(s) = 0$. So the only summands which contribute to $(\mu \ast 1)(n)$ those with $d_i \in \{0,1\}$. Moreover, in this case, the value of $\mu(s)$ depends only on whether the number of nonzero $d_i$ is even or odd. There are $2^k$ subsets of $\{1,\ldots,k\}$, half of which have an even number of elements and half odd. So $\sum_{s|n} \mu(s) = \sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|}$ $= 0$. Hence $\mu \ast 1 = \delta_{1,n}$. $\square$

Now given $f : \mathbb{N}^+ \rightarrow M$, define $F = 1 \ast f$– so $F(n) = \sum_{d|n} f(d)$. Then $\mu \ast F = (\mu \ast 1) \ast f$ $= f$.

Now let $M$ be the abelian group $F(x)^\times$. (The nonzero rational functions over $F$ in one variable). This is an abelian group, hence a $\mathbb{Z}$-module, where we write our operator multiplicatively and our $\mathbb{Z}$-action by exponentiation. Let $f : \mathbb{N}^+ \rightarrow M$ be given by $f(n) = \Phi_n(x)$, and let $F(n) = (1 \ast f)(n) = \sum_{d|n} \varphi_n(x)$ $= x^n-1$. Now $\mu \ast F = f$, which expanded out gives the identity $\Phi_n(x) = \prod_{st=n} (x^s-1)^{\mu(t)}$ as desired.

### A fact about cyclotomic polynomials

Let $n > 1$ be an odd integer. Prove that $\Phi_{2n}(x) = \Phi_n(-x)$, where $\Phi_n(x)$ denotes the $n$th cyclotomic polynomial.

We begin with a lemma.

Lemma: -1 is not an $n$th root of unity for odd $n$. Proof: $(-1)^n-1=-1-1=-2$. $\square$

Let $\zeta$ be a primitive $n$th root of unity. Now suppose $(-\zeta)^t = 1$, so that $(-1)^t\zeta^t = 1$, so $\zeta^t = (-1)^t$. Since $\zeta$ is a primitive $n$th root of unity, with $n$ odd, the powers of $\zeta$ are $n$th roots of unity. By the lemma, we must have $(-1)^t = 1$, so that $2|t$, and thus $\zeta^t=1$, so that $n|t$. Since $2$ and $n$ are relatively prime, $2n|t$, and so $-\zeta$ is a primitive $2n$th root of unity.

In particular, $\Phi_n(-x)$ divides $\Phi_{2n}(x)$.

Now $\Phi_n(-x)$ has degree $\varphi(n)$, and $\Phi_{2n}(x)$ has degree $\varphi(2n)$, where $\varphi$ denotes the Euler totient. Since $2$ and $n$ are relatively prime, we have $\varphi(2n) = \varphi(2)\varphi(n) = \varphi(n)$. So in fact $\varphi_{2n}(x) = \varphi_n(-x)$.

### Finite extensions of the rationals contain only finitely many roots of unity

Let $K$ be a finite extension of $\mathbb{Q}$. Prove that $K$ contains only finitely many roots of unity.

Suppose to the contrary that $K$ contains infinitely many roots of unity. Now for each $n$, there are only finitely many primitive roots of unity (in fact $\varphi(n)$ of them). So for each $m$, the number of primitive roots of unity of order at most $m$ is finite. In particular, for any $m$, there exists a primitive $n$th root of unity for some $n > m$.

Let $m$ be the degree of $K$ over $\mathbb{Q}$. If $\zeta \in K$ is a primitive $k$th root of unity, then $[\mathbb{Q}(\zeta):\mathbb{Q}] = \varphi(k)$ by Corollary 42 on page 555, where $\varphi$ denotes the Euler totient. By this previous exercise, since $k$ is arbitrarily large, $\varphi(k)$ is arbitrarily large. So there exists a primitive $k$th root $\zeta$ such that $\varphi(k) > m$, a contradiction since $\mathbb{Q}(\zeta) \subseteq K$.

### There are m distinct pᵏmth roots of unity over a field of characteristic p, for p a prime not dividing m

Let $n = p^km$, where $p$ is a prime not dividing $m$, and let $F$ be a field of characteristic $p$. Prove that there are $m$ distinct $n$th roots of unity over $F$.

Note that $x^n-1 = x^{p^km}-1$ $= (x^m)^{p^k}-1$ $= (x^m-1)^{p^k}$. That is, the distinct $n$th roots of unity over $F$ are precisely the distinct roots of $x^m-1$ over $F$.

If $m=1$, then certainly there is only 1 root of $x-1$.

Suppose $m > 1$. Now $D(x^m-1) = mx^{m-1}$, which has only the root 0 with multiplicity $m-1$. Clearly 0 is not a root of $x^m-1$, so that $x^m-1$ and its derivative are relatively prime, and thus $x^m-1$ is separable. Hence there are $m$ distinct $m$th roots of unity over $F$, and so $m$ distinct $n$th roots of unity over $F$.

### Any field containing the nth roots of unity for odd n also contains the 2nth roots of unity

Let $F$ be a field over which $x^n-1$ splits where $n$ is odd. Show that $x^{2n}-1$ also splits over $F$.

Note that $x^{2n}-1 = (x^n)^2-1 = (x^n+1)(x^n-1)$.

Since $n$ is odd, if $\zeta$ is a root of $x^n-1$, then $(-\zeta)^n+1 = -\zeta^n+1 = 0$. That is, the roots of $x^n+1$ are precisely the negatives of the roots of $x^n-1$ (note that these are all distinct, since the derivative of $x^n-1$ has no nonzero roots). So any field containing the roots of $x^n-1$ also contains the roots of $x^{2n}-1$.

### If ζ is a primitive nth root of unity and d divides n, then ζᵈ is a primitive (n/d)th root of unity

Let $\zeta$ be a primitive $n$th root of unity and let $d|n$. Prove that $\zeta^d$ is a primitive $n/d$th root of unity.

Certainly $(\zeta^d)^{n/d} = 1$. Now if $(\zeta^d)^t = 1$, we have $n|dt$, and so $n/d$ divides $t$. So $n/d$ is the order of $\zeta^d$, and thus $\zeta^d$ is a primitive $n/d$th root of unity.

### If m and n are relatively prime, the product of a primitive mth root of unity and a primitive nth root of unity is a primitive mnth root of unity

Suppose $m$ and $n$ are relatively prime, and let $\zeta_m$ and $\zeta_n$ be primitive $m$th and $n$th roots of unity, respectively. Show that $\zeta_m\zeta_n$ is a primitive $mn$th root of unity.

Note first that $(\zeta_m\zeta_n)^{mn} = (\zeta_m^m)^n (\zeta_n^n)^m = 1$, so that $\zeta_m\zeta_n$ is an $mn$th root of unity.

Now let $t$ be the order of $\zeta_m\zeta_n$; we have $(\zeta_m\zeta_n)^t = 1$, so that $\zeta_m^t = \zeta_n^{-t}$. In particular, $\zeta_m^t$ and $\zeta_n^{-t}$ have the same order, which must be a divisor of both $m$ and $n$. Since $m$ and $n$ are relatively prime, the order of $\zeta_m^t$ is 1, so $\zeta_m^t = 1$. Likewise $\zeta_n^t = 1$. So $m|t$ and $n|t$, and again since $m$ and $n$ are relatively prime, $mn|t$. So $|\zeta_m\zeta_n| = mn$, and $\zeta_m\zeta_n$ is a primitive $mn$th root of unity.