Homework 12 (Extra Credit)

Note: This assignment is extra credit, with each problem worth the indicated number of points on the final exam. You can turn in none, some, or all of the problems. As with any homework assignment, feel free to work together with other students in the class when solving these problems.

1. [5 points] Prove that \(x^p-x-1\) is irreducible over \(\mathbb{Z}_p\) for any prime \(p\).
   (Hint: Use Corollary 8 from the “Classification of Finite Fields” notes.)
2. [10 points] Let \(p\) be a prime congruent to 7 modulo 9, let \(\omega\in\mathbb{Z}_p^\times\) be an element of order 3, and let \(a\) be a perfect cube in \(\mathbb{Z}_p^\times\) (i.e. a nonzero cubic residue).
   1. Prove that neither \(\omega a\) nor \(\omega^2 a\) has a cube root in \(\mathbb{Z}_p^\times\).
   2. Prove that \(a^{(p+2)/9}\) is a cube root of \(a\) modulo \(p\).
   3. Use part (b) to find a cube root of 1566402791096 modulo 5716135896379.
3. [15 points] The goal of this problem is to prove the following theorem.

   Theorem. For any positive integer \(n\), there are infinitely many primes congruent to 1 modulo \(n\).

   1. Let \(p\) be a prime, let \(n\geq 1\), and suppose that \(p\,{\not|}\; n\). Prove that every root of the cyclotomic polynomial \(\Phi_n(x)\) in \(\mathbb{Z}_p\) must have order \(n\).
      (Hint: Combine Proposition 10 from the “Classification of Finite Fields” notes with Theorem 19 from the notes on cyclotomic polynomials.)
   2. Prove that if \(j\) and \(n\) are positive integers then \(\gcd\bigl(j,\Phi_n(j)\bigr) = 1\).
   3. If \(n\) and \(k\) are positive integers, use parts (a) and (b) to prove that every prime factor of \(\Phi_n(nk)\) is congruent to 1 modulo \(n\).
   4. Use parts (b) and (c) to prove the theorem.
      (Hint: Use a variation of Euclid's proof of the infinitude of primes. Note that \(\Phi_n(a)\) is monic, so \(\Phi_n(a) > 1\) for sufficiently large values of \(a\).)