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 mth and nth roots of unity, respectively. Show that \zeta_m\zeta_n is a primitive mnth 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 mnth 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 mnth root of unity.

A fact about polynomials over a perfect field

Let K be an extension of F, with F a perfect field. Suppose p(x) \in F[x] has no repeated irreducible factors; prove that p(x) has no repeated irreducible factors in K[x].


Suppose p has no repeated irreducible factors. Since F is perfect, the irreducible factors of p are separable (Prop. 37 on 549 in D&F), and so p is separable. (If not, then it would have a repeated irreducible factor.) That is, p has no repeated roots.

Now if p has a repeated irreducible factor over K, then it has repeated roots- a contradiction.

A fact about multivariate polynomials over ZZ

Let f(x_1,\ldots,x_n) \in \mathbb{Z}[x_1,\ldots,x_n], and let p be a prime. Prove that f(x_1,\ldots,x_n)^p = f(x_1^p,\ldots,x_n^p) mod p.


Remember that \alpha^p \equiv \alpha mod p for all \alpha. Say f = \sum_i c_i \prod_j x_j^{e_{i,j}}.

Then f(x_1,\ldots,x_n)^p = (\sum_i c_i \prod_j x_j^{e_{i,j}})^p = \sum_i c_i^p \prod_j x_j^{e_{i,j}p} = \sum_i c_i \prod_j (x_j^p)^{e_{i,j}} = f(x_1^p,\ldots,x_n^p) as desired.

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.

Over an imperfect field of characteristic p, there exist irreducible inseparable polynomials

Let K be an imperfect field of characteristic p. Prove that there exist irreducible inseparable polynomials over K. Conclude that there exist inseparable finite extensions of K.


Let \alpha \in K be an element which is not a pth power in K, and let \zeta be a root of x^p-\alpha. In particular, \zeta \notin K. Now consider q(x) = (x-\zeta)^p = x^p-\alpha. Suppose t(x) is an irreducible factor of q over K. Now t cannot be linear, since \zeta \notin K. But any factor of q of degree at least 2 has a multiple root (since all the roots are \zeta). So t is an irreducible inseparable polynomial over K.

Then K(\zeta) is an inseparable extension of K.

Wilson’s Theorem

Prove that x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha). Conclude that \prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}. Deduce Wilson’s Theorem: if p is an odd prime, then (p-1)! \equiv -1 mod p.


Recall that x^{p^n}-x = \prod_{\alpha \in \mathbb{F}_{p^n}^\times}(x-\alpha) by definition, and that 0 \in \mathbb{F}_{p^n} is merely the root having minimal polynomial x. So x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha). Comparing constant coefficients, we have \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (-\alpha) = -1, so that $latex (-1)^{p^n-1} \prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = -1, and hence \prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}.

Restrict now to the field \mathbb{F}_p \cong \mathbb{Z}/(p) with p odd. Then \prod_{\alpha \in \mathbb{F}_p} \alpha = (p-1)!, and (-1)^p = -1. Thus (p-1)! \equiv -1 mod p.

(I’d like to point out that this is a really roundabout way to prove Wilson’s Theorem. The easy(ier) way is to note that in \mathbb{Z}/(p)^\times, every element but -1 is distinct from its inverse.)

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

xᵈ-1 divides xⁿ-1 if and only if d divides n

Prove that x^d-1 divides x^n-1 if and only if d divdes n.


Suppose d|n; say n = dt.

If t = 1, there is nothing to show. Suppose t > 1; then x^n-1 = (x^d)^t - 1 = (x^d-1)(\sum_{i=0}^{t-1} (x^d)^i), so that x^d-1 divides x^n-1.

Now suppose x^d-1 divides x^n-1. By the Division Algorithm in \mathbb{N}, we have q and r such that n = qd+r. Now x^n-1 = x^{qd}x^r - 1 = x^{qd}x^r -x^r + x^r - 1 = x^r(x^{qd}-1) + (x^r-1). If q=1, then (by the uniqueness part of the division algorithm in \mathbb{Q}[x]) x^r-1 = 0, so r = 0 and d|n. If q > 1, then x^n - 1 = x^r(x^d-1)(\sum_{i=0}^{q-1} (x^d)^i) + (x^r-1), and again we have r = 0, so d|n.