Math 361, Spring 2022, Assignment 14

Describe the following procedures:

1. Sieve of Eratosthenes (for integers).
2. Sieve of Eratosthenes (for polynomials with coefficients in a finite field).
3. Procedure to factor polynomials over $\mathbb{C}$.
4. Procedure to factor polynomials over $\mathbb{R}$.

Solve the following problems:

1. Skim the introduction to the Wikipedia article on polynomial factorization so you will know where to find search terms when you one day need to know how to factor high-degree polynomials.
2. Working over $\mathbb{Z}_2$, factor the polynomial $x^3+1$ into irreducibles. (Hint: first look for roots and pull out the corresponding linear factors by long division.)
3. Repeat the previous exercise for $x^4+1$ and for $x^5+1$. (Hint: the hardest part will be deciding whether $x^4+x^3+x^2+x+1$ can be factored as the product of two quadratics. But for this, you can make a list of all irreducible quadratics and test for divisibility by each in turn.)
4. Working over $\mathbb{Z}_3$, find all irreducible polynomials of degree two. (Hint: you do not need the Sieve; you just need to find quadratics that have no roots.)
5. Construct a field with nine elements.

--------------------End of assignment--------------------