The smallest degree of a factor of a cyclotomic polynomial mod a prime

Let \ell be a prime and let \Phi_\ell(x) = \dfrac{x^\ell-1}{x-1} \in \mathbb{Z}[x] be the \ellth cyclotomic polynomial. In this exercise, we will determine the smallest degree of a factor of \Phi_\ell mod p, and in particular determine when \Phi_\ell is irreducible mod p. (Recall that \Phi_\ell is irreducible over \mathbb{Q} by Eisenstein’s criterion.)

  1. Show that if p = \ell then \Phi_\ell is divisible by x-1 in \mathbb{F}_\ell[x].
  2. Suppose p \neq \ell and let f denote the order of p in \mathbb{F}_\ell^\times (that is, f is minimal such that p^f \equiv 1 mod \ell$). Show that f is minimal such that \mathsf{GL}_f(\mathbb{F}_p) contains an element A of order \ell.
  3. Show that \Phi_\ell is not divisible by any polynomial of degree smaller than f in \mathbb{F}_p[x]. Let m_A(x) \in \mathbb{F}_p[x] denote the minimal polynomial for a matrix A as in (2) and conclude that m_A(x) is irreducible of degree f and divides \Phi_\ell(x) in \mathbb{F}_p[x].
  4. Prove that \Phi_\ell(x) is irreducible mod p if and only if \ell-1 is the smallest power of p which is congruent to 1 mod \ell; that is, p is a primitive root mod \ell.

  1. As we showed in this previous exercise, (x-1)^\ell = x^\ell - 1 in \mathbb{F}_\ell[x]. So we have \Phi_\ell(x) = (x-1)^{\ell-1}.
  2. Suppose f is the order of p mod \ell. Recall that |\mathsf{GL}_f(\mathbb{F}_p)| = \prod_{i=1}^f (p^f - p^{f-i}). In particular, |\mathsf{GL}_f(\mathbb{F}_p)| \equiv 0 mod \ell since p^f - 1 \equiv 0. By Cauchy’s Theorem, there exists an element A of order \ell in \mathsf{GL}_f(\mathbb{F}_p).

    Now suppose \mathsf{GL}_m(\mathbb{F}_p) has an element A of order \ell. Then we have \prod_{i=1}^m (p^m - p^{m-i}) \equiv 0 mod \ell, and so p^m - p^{m-i} \equiv 0 mod \ell for some i. Then p^i \equiv 0 mod \ell. If m < f, we have a contradiction, since f is minimal such that p^f \equiv 1 mod \ell.

  3. Suppose \Phi_\ell(x) is divisible by a polynomial q(x) of degree m < f over \mathbb{F}_p. Then the companion matrix of q has dimension m < f and satisfies x^\ell - 1 = 0. This contradicts (2), which showed that f is minimal such that \mathsf{GL}_f(\mathbb{F}_p) contains an element of order \ell.

    Now let m_A(x) be the minimal polynomial of the matrix A of order \ell in \mathsf{GL}_f(\mathbb{F}_p). The degree of m_A is at least f, by the first paragraph of (3). Moreover the degree of m_A is at most f, since the characteristic polynomial of A has degree f. So the degree of m_A is exactly f. Moreover, m_A must be irreducible, since any proper divisor of m_A also divides \Phi_\ell(x) over \mathbb{F}_p and has degree less than f.

  4. By part (3), the smallest degree of a (nonunit) divisor of \Phi_\ell(x) over \mathbb{F}_p is precisely the order of p mod \ell. So \Phi_\ell is irreducible over \mathbb{F}_p if and only if the order of p mod \ell is \ell-1; that is, if p is a generator of \mathbb{F}_\ell or a primitive \ellth root of 1.
Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: