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.