Let be a prime and let be the th cyclotomic polynomial. In this exercise, we will determine the smallest degree of a factor of mod , and in particular determine when is irreducible mod . (Recall that is irreducible over by Eisenstein’s criterion.)
- Show that if then is divisible by in .
- Suppose and let denote the order of in (that is, is minimal such that mod \ell$). Show that is minimal such that contains an element of order .
- Show that is not divisible by any polynomial of degree smaller than in . Let denote the minimal polynomial for a matrix as in (2) and conclude that is irreducible of degree and divides in .
- Prove that is irreducible mod if and only if is the smallest power of which is congruent to 1 mod ; that is, is a primitive root mod .
- As we showed in this previous exercise, in . So we have .
- Suppose is the order of mod . Recall that . In particular, mod since . By Cauchy’s Theorem, there exists an element of order in .
Now suppose has an element of order . Then we have mod , and so mod for some . Then mod . If , we have a contradiction, since is minimal such that mod .
- Suppose is divisible by a polynomial of degree over . Then the companion matrix of has dimension and satisfies . This contradicts (2), which showed that is minimal such that contains an element of order .
Now let be the minimal polynomial of the matrix of order in . The degree of is at least , by the first paragraph of (3). Moreover the degree of is at most , since the characteristic polynomial of has degree . So the degree of is exactly . Moreover, must be irreducible, since any proper divisor of also divides over and has degree less than .
- By part (3), the smallest degree of a (nonunit) divisor of over is precisely the order of mod . So is irreducible over if and only if the order of mod is ; that is, if is a generator of or a primitive th root of 1.