Tag Archives: finite field

pn choose pk and n choose k are congruent mod p

Show that $\binom{pn}{pk} \equiv \binom{n}{k}$ mod $p$.

Note that $(1+x)^{pn} = \sum_{t=0}^{pn} \binom{pn}{t}x^t$ by the binomial theorem. The coefficient of $x^{pk}$ is $\binom{pn}{pk}$. Over $\mathbb{F}_p$, we have $(1+x)^{pn} = ((1+x)^p)^n$ $= (1+x^p)^n$ $= \sum_{t=0}^n \binom{n}{t}(x^p)^t$, and now the coefficient of $x^{pk}$ is $\binom{n}{k}$. In particular, we have $\binom{pn}{pk} \equiv \binom{n}{k}$ mod $p$.

f(x)ᵖ = f(xᵖ) over ZZ/(p)

Prove that $f(x)^p = f(x^p)$ for all $f(x) \in \mathbb{F}_p[x]$.

Let $f(x) = \sum c_ix^i$. Remember that the elements of $\mathbb{F}_p$ are precisely the roots of $x^p-x$; in particular, $\alpha^p = \alpha$ for all $\alpha \in \mathbb{F}_p$.

Then $f(x)^p = (\sum c_ix^i)^p$ $= \sum (c_ix^i)^p$ $= \sum c_i^p(x^i)^p$ $= \sum c_i (x^p)^i$ $= f(x^p)$ as desired.

xᵖ-x+a is irreducible and separable over ZZ/(p)

Prove that for any prime $p$ and any nonzero $a \in \mathbb{F}_p$, $q(x) = x^p-x+a$ is irreducible and separable over $\mathbb{F}_p$.

Note that $D_x(q) = px^{p-1}-1 = -1$, so that $q$ and $D(q)$ are relatively prime. So $q$ is separable.

Now let $\alpha$ be a root of $q$. Using the Frobenius endomorphism, $(\alpha+1)^p-(\alpha+1)+a = \alpha^p - \alpha + a = 0$, so that $\alpha+1$ is also a root. By induction, $\alpha_k$ is a root for all $k \in \mathbb{F}_p$, and since $q$ has degree $p$, these are all of the roots.

Now $\mathbb{F}_p(\alpha+k) = \mathbb{F}_p(\alpha)$, and in particular the minimal polynomials of $\alpha$ and $\alpha+k$ have the same degree over $\mathbb{F}_p$ – say $d$. Since $q$ is the product of the minimal polynomials of its roots, we have $p = dt$ for some $t$. Since $p$ is prime, we have either $d=1$ (so that $\alpha \in \mathbb{F}_p$, a contradiction) or $d=p$, so that $q$ itself is the minimal polynommial of $\alpha$, hence is irreducible.

If a is an integer greater than 1, then aᵈ-1 divides aⁿ-1 if and only if d divides n

Fix an integer $a > 1$. Prove that for all $d,n \in \mathbb{N}$, $d$ divides $n$ if and only if $a^d-1$ divides $a^n-1$. Conclude that $\mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}$ if and only if $d|n$.

If $d|n$, then by this previous exercise, $x^d-1$ divides $x^n-1$ in $\mathbb{Z}[x]$, and so $a^d-1$ divides $a^n-1$ in $\mathbb{Z}$.

Conversely, suppose $a^d-1$ divides $a^n-1$. Using the Division Algorithm, say $n = qd+r$. Now $a^n-1 = (a^d)^qa^r - a^r + a^r - 1$ $= a^r((a^d)^q-1) + (a^r-1)$. If $q = 1$, then we have $a^r-1 = 0$, so that $r = 0$ and $d|n$. If $q > 1$, then $a^n-1 = a^r(a^d-1)(\sum_{i=0}^{q-1} (a^d)^i) + (a^r-1)$, and again we have $r = 0$, so that $d|n$ as desired.

Recall that $\mathbb{F}_{p^k}$ is precisely the roots (in some splitting field) of $x^{p^k}-x$. Now $d|n$ if and only if $p^d-1$ divides $p^n-1$ by the above argument, if and only if $x^{p^d-1}-1$ divides $x^{p^n-1}-1$ by a previous exercise, if and only if $x^{p^d}-x$ divides $x^{p^n}-x$, if and only if $\mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}$.

Find the irreducible polynomials of degree 1, 2, and 4 over ZZ/(2)

Find all the irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$, and verify that their product is $x^{16}-x$.

Note that there are $2^k$ (monic) polynomials of degree $k$, as each non-leading coefficient can be either 0 or 1.

The polynomials of degree 1, $p_1(x) = x$ and $p_2(x) = x+1$, are both irreducible.

There are 4 polynomials of degree 2, one of which is irreducible.

1. $x^2 = xx$ is reducible
2. $x^2+1 = (x+1)^2$ is reducible
3. $x^2+x = x(x+1)$ is reducible
4. $p_3(x) = x^2+x+1$ has no roots, and so is irreducible.

Before we address the degree 4 polynomials, we prove a lemma.

Lemma 1: If $p(x)$ is a degree 4 polynomial over $\mathbb{F}_2$ with constant term 1 and $p$ factors as a product of quadratics, then the linear and cubic terms of $p$ are equal. Proof: We have (as we assume) $p(x) = (x^2+ax+b)(x^2+cx+d)$ $= x^4 + (a+c)x^3 + (b+d+ac)x^2 + (ad+bc)x+bd$. Now $bd = 1$, so that $b = d = 1$. So $p(x) = x^4 + (a+c)x^3 + acx^2 + (a+c)x + 1$, as desired. $\square$

Lemma 2: $\Phi_5(x) = x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$. Proof: Clearly this has no roots. By Lemma 1, if $\Phi_5(x)$ factors into two quadratics, then the factors’ linear terms, $a$ and $c$, satisfy $a+c=ac=1$, which is impossible over $\mathbb{F}_2$. $\square$

There are 16 polynomials of degree 4.

1. $x^4 = xx^3$ is reducible
2. $x^4+1 = (x^2+1)^2$ is reducible
3. $x^4+x = x(x^3+1)$ is reducible
4. $x^4+x^2 = x^2(x^2+1)$ is reducible
5. $x^4+x^3 = x^3(x+1)$ is reducible
6. $p_4(x) = x^4+x+1$ clearly has no roots, and by the lemma, has no quadratic factors. So $p_4$ is irreducible.
7. $x^4+x^2+1 = (x^2+x+1)^2$ is reducible
8. $p_5(x) = x^4+x^3+1$ clearly has no roots, and by Lemma 1, has no quadratic factors. So $p_5$ is irreducible.
9. $x^4+x^2+x = x(x^3+x+1)$ is reducible
10. $x^4+x^3+x = x(x^3+x^2+1)$ is reducible
11. $x^4+x^3+x^2 = x^2(x^2+x+1)$ is reducible
12. $x^4+x^2+x+1$ has 1 as a root, so is reducible
13. $x^4+x^3+x^2+1 = (x+1)(x^3+1)$ is reducible
14. $x^4+x^3+x^2+1$ has 1 as a root, so is reducible
15. $x^4+x^3+x^2+x = x(x^3+x^2+x+1)$ is reducible
16. $p_6(x) = x^4+x^3+x^2+x+1 = \Phi_5(x)$ is irreducible

So there are six irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$:

1. $p_1(x) = x$
2. $p_2(x) = x+1$
3. $p_3(x) = x^2+x+1$
4. $p_4(x) = x^4+x+1$
5. $p_5(x) = x^4+x^3+1$
6. $p_6(x) = x^4+x^3+x^2+x+1$

It is easy (if tedious) to verify that the product of these polynomials is $x^{16}-x$. (WolframAlpha agrees.)

Exhibit some finite fields

Let $g(x) = x^2+x-1$ and $h(x) = x^3-x+1$. Construct finite fields of order 4, 8, 9, and 27 elements. For the fields with 4 and 9 elements, give the multiplication tables and show that the nonzero elements form a cyclic group.

Note that to construct fields of the given sizes, it suffices to show that $g(x)$ and $h(x)$ are each irreducible over the fields $\mathbb{F}_2$ and $\mathbb{F}_3$. (More precisely, that these polynomials are irreducible when we inject the coefficients into the respective fields.)

It is easy to see that neither $g$ nor $h$ has a root in either $\mathbb{F}_2$ or in $\mathbb{F}_3$, so these are indeed irreducible. Then $\mathbb{F}_2[x]/(g(x))$, $\mathbb{F}_2[x]/(h(x))$, $\mathbb{F}_3[x]/(g(x))$, and $\mathbb{F}_3[x]/(h(x))$ are fields of order 4, 8, 9, and 27 by Proposition 11 in D&F, and specifically are isomorphic as fields to the extension of $\mathbb{F}_2$ or $\mathbb{F}_3$ by adjoining a root of $g$ or $h$.

The multiplication table of $\mathbb{F}_2(\alpha) \cong \mathbb{F}_2[x]/(g(x))$ is as follows.

 $\begin{array}{c|cccc} & 0 & 1 & \alpha & \alpha+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & \alpha+1 \\ \alpha & 0 & \alpha & \alpha+1 & 1 \\ \alpha+1 & 0 & \alpha+1 & 1 & \alpha \end{array}$

Evidently, $(\mathbb{F}_2(\alpha))^\times$ is generated by $\alpha$.

The multiplication table of $\mathbb{F}_3(\alpha) \cong \mathbb{F}_3[x]/(g(x))$ is as follows.

 $\begin{array}{c|ccccccccc} & 0 & 1 & 2 & \alpha & \alpha+1 & \alpha+2 & 2\alpha & 2\alpha+1 & 2\alpha+2 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & \alpha & \alpha+1 & \alpha+2 & 2\alpha & 2\alpha+1 & 2\alpha+2 \\ 2 & 0 & 2 & 1 & 2\alpha & 2\alpha+2 & 2\alpha+1 & \alpha & \alpha+2 & \alpha+1 \\ \alpha & 0 & \alpha & 2\alpha & 2\alpha+1 & 1 & \alpha+1 & \alpha+2 & 2\alpha+2 & 2 \\ \alpha+1 & 0 & \alpha+1 & 2\alpha+2 & 1 & \alpha+2 & 2\alpha & 2 & \alpha & 2\alpha+1 \\ \alpha+2 & 0 & \alpha+2 & 2\alpha+1 & \alpha+1 & 2\alpha & 2 & 2\alpha+2 & 1 & \alpha \\ 2\alpha & 0 & 2\alpha & \alpha & \alpha+2 & 2 & 2\alpha+2 & 2\alpha+1 & \alpha+1 & 1 \\ 2\alpha+1 & 0 & 2\alpha+1 & \alpha+2 & 2\alpha+2 & \alpha & 1 & \alpha+1 & 2 & 2\alpha \\ 2\alpha+2 & 0 & 2\alpha+2 & \alpha+1 & 2 & 2\alpha+1 & \alpha & 1 & 2\alpha & \alpha+2 \end{array}$

Evidently, $(\mathbb{F}_3(\alpha))^\times$ is generated by $\alpha$.

Every finite field has prime power order

Let $F$ be a finite field of characteristic $p$. Prove that $|F| = p^n$ for some $n$.

Suppose $F$ has a nonzero element $\alpha$ of additive order $q$. That is, $q$ is minimal such that $q\alpha = 0$. Note that $q \leq p$, since $p$ annihilates every element of $F$ (being the characteristic of $F$). If $q < p$, then by the division algorithm in $\mathbb{Z}$ we have $p = qb + r$ for some $b$ and $r$ with $0 \leq r < q$. If $r \neq 0$, then $r \alpha = 0$, violating the minimalness of $q$. If $r = 0$, then $p = qb$. Since $p$ is prime, either $q = 1$ (so $\alpha = 0$) or $b = 1$ (so $q = p$), which both give a contradiction. Thus $q = p$.

So every element of $F$ has additive order $p$, and thus by Cauchy’s theorem $|F|$ is a power of $p$.

Compute the Jordan canonical form of a given matrix over a finite field

Let $p$ be a prime. Compute the Jordan canonical form over $\mathbb{F}_p$ of the $n \times n$ matrix whose diagonal entries are 0 and whose off-diagonal entries are 1. ($n \geq 2$)

Let $A = [1 - \delta_{i,j}]$. The computation we carried out here shows that $(A - (n-1)I)(A+I) = 0$ over $\mathbb{F}_p$ (indeed, over any ring with 1). So the minimal polynomial of $A$ divides $(x-(n-1))(x+1)$. Note that $A-(n-1)I$ and $A+I$ are nonzero (any off-diagonal entry is 1), so the minimal polynomial of $A$ is precisely $m(x) = (x-(n-1))(x+1)$.

Let $V = \mathbb{F}_p^n$ be an $\mathbb{F}_p[x]$-module via $A$ as usual. Now the invariant factors $m_k(x)$ of $V$ divide $m(x)$, and we have $V = \bigoplus_k \mathbb{F}[x]/(m_k(x))$.

We claim that $(A+I)V$ has dimension 1 over $\mathbb{F}_p$. Indeed, if $v = [v_1\ \ldots\ v_n]^\mathsf{T}$, then $(A+I)v = (\sum v_i)[1\ \ldots\ 1]^\mathsf{T}$.

Using Lemmas 2 and 3 from this previous exercise, we have $(x+1)V = \bigoplus_k (x+1)\mathbb{F}_p[x]/(m_k(x))$ $\cong_{\mathbb{F}_p[x]} \bigoplus_{(x+1)|m_k} \mathbb{F}_p[x]/(m_k/(x+1)) \oplus \bigoplus_{(x+1,m_k) = 1} \mathbb{F}_p[x]/(m_k(x))$. Note that any mapping which realizes an isomorphism as $\mathbb{F}_p[x]$-modules is necessarily also an $\mathbb{F}_p$-vector space isomorphism; since $(A+I)V$ has dimension 1, the right hand side of this isomorphism also has dimension 1 over $\mathbb{F}_p$. Now one of the left summands is $\mathbb{F}_p[x]/(x-(n-1))$, corresponding to the minimal polynomial. Thus the remaining summands must be trivial; that is, there are no invariant factors which are not divisible by $x+1$, and every invariant factor other than the minimal polynomial is exactly $x+1$.

So the elementary divisors of $A$ are $x+1$ ($n-1$ times) and $x-(n-1)$. The corresponding Jordan canonical form is $J = [b_{i,j}]$ where $b_{i,j} = n-1$ if $i=j=n$, $-1$ if $i=j \neq n$, and $0$ otherwise.

Compute the Jordan canonical form of a given matrix over a finite field

Let $p$ be a prime. Compute the Jordan canonical form over the finite field $\mathbb{F}_p$ of the $n \times n$ matrix whose every entry is 1. ($n \geq 2$.)

Let $A = [1]$. Now the computation in this previous exercise holds over $\mathbb{F}_p$ (indeed, over any ring with 1), and so we have $A(A-nI) = 0$.

If $n$ is not divisible by $p$, then $n$ is a unit in $\mathbb{F}_p$. If $v = [v_1\ \ldots\ v_n]^\mathsf{T}$ is an eigenvector with eigenvalue $n$, then evidently (as we saw in the exercise referenced above) $v = v_1[1\ \ldots\ 1]^\mathsf{T}$. So the eigenspace of $n$ has dimension 1, the characteristic polynomial of $A$ is $x^{n-1}(x-n)$, and the Jordan canonical form of $A$ is $J = [b_{i,j}]$ where $b_{n,n} = n$ and $b_{i,j} = 1$ otherwise.

Suppose $p$ divides $n$. Since $A \neq 0$, the minimal polynomial of $A$ is now $x^2$. We claim that the remaining invariant factors of $A$ are $x$. There is probably a slick linear-algebraic way to argue this, but I don’t see it. Instead I will show explicitly that $A$ is similar to a matrix in Jordan canonical form. (If anyone can offer a simplification of this proof I’d be grateful!)

If $n = 2$, then the minimal polynomial of $A$ is the only invariant factor, so the Jordan form of $A$ is $\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$. Suppose $n \geq 2$.

Let $U = [1\ \ldots\ 1]^\mathsf{T}$ have dimension $(n-1) \times 1$, and let $W$ be the $(n-1) \times (n-1)$ matrix whose every entry is 1. Note that $UU^\mathsf{T} = W$ and $U^\mathsf{T}U = [n-1]$. Let $P = \begin{bmatrix} 1 & 0 \\ U & I \end{bmatrix}$ and $Q = \begin{bmatrix} 1 & 0 \\ -U & I \end{bmatrix}$. Evidently $QP = I$, so that $Q = P^{-1}$. Moreover, we have $A = \begin{bmatrix} 1 & U^\mathsf{T} \\ U & W \end{bmatrix}$, and $P^{-1}AP = B = \begin{bmatrix} n & U^\mathsf{T} \\ 0 & 0 \end{bmatrix}$ $= \begin{bmatrix} 0 & U^\mathsf{T} \\ 0 & 0 \end{bmatrix}$.

Now let $V = [1\ \ldots\ 1]$ have dimension $1 \times (n-2)$. Let $R = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -V \\ 0 & 0 & I \end{bmatrix}$ and $S = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & V \\ 0 & 0 & I \end{bmatrix}$. Evidently, $RS = I$, so that $S = R^{-1}$. Now $B = \begin{bmatrix} 0 & 1 & V \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$, and we have $R^{-1}BR = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$. If we squint just right, this matrix is in Jordan canonical form, and is similar to $A$.

Show that two matrices over a finite field are similar

Let $p$ be a prime. Show that the following $p \times p$ matrices are similar in $\mathsf{Mat}_p(\mathbb{F}_p)$: $A = \mathcal{C}_{x^p-1}$ (the companion matrix of $x^p-1$) and $B = J_p(1)$ (the $p \times p$ Jordan block with eigenvalue 1).

Recall that the characteristic polynomial of $\mathcal{C}_{x^p-1}$ is $x^p-1$ (as we showed here), and that over $\mathbb{F}_p$ we have $x^p-1 = (x-1)^p$ (as can be deduced from this precious exercise).

We claim that in fact $x^p-1$ is the minimal polynomial of $A$. Recall (from this previous exercise) that $\mathsf{Sym}(p)$ (the symmetric group on $p$ objects) is embedded in $\mathsf{GL}_p(\mathbb{F}_p)$ by letting a permutation $\sigma$ act index-wise on the elements of an ordered basis (i.e. $\sigma \cdot e_i = e_{\sigma(i)}$). Now $A$ is in the image of this representation, and in fact is the matrix representing the permutation whose cycle decomposition is $\sigma = (1\ 2\ 3\ \ldots\ p-1\ p)$. In particular, $A^{p-1} = A^{-1}$ is not the identity transformation, so the minimal polynomial of $A$ is indeed $x^p-1$.

So the elementary divisors of $A$ are just $(x-1)^p$, and so $A$ is similar to the Jordan block $B$.