189-235A: Basic Algebra I Assignment 3

Due: Monday, October 21

1. Perform the Euclidean algorithm to find the gcd of f(x) = x^{4} + 3x^{3} + 16x^{2} + 33x + 55 and g(x) = x^{3} + x^{2} − x − 10 in the polynomial ring Q[x]. Write this greatest common divisor as a linear combination of f(x) and g(x) with coefficients in Q[x].

2. Same question as 1, with f(x) = x^{6} + x^{4} + x + 1 and g(x) = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1 in Z/2Z[x].

3. List all the irreducible polynomials of degree 4 in Z/2Z[x].

4. If p is an odd prime of the form 1 + 4m, use Wilson’s Theorem to show that a = (2m)! is a root in Z/pZ of the polynomial x^{2} + 1 in Z/pZ[x].

5. In class, we showed that a polynomial of degree d with coefficients in a field F has at most d roots. Show that this statement ceases to be true when F is replaced by an arbitrary ring, such as the ring Z/nZ of residue classes modulo n with n a composite integer.

6. Let d be a fixed integer. Let n = pq ∈ Z be an integer which is a product of two distinct primes, p and q, and let f ∈ Z/nZ[x] be a monic polynomial with coefficients in Z/nZ of degree d. Give a “best possible” general upper bound (as a function of d) for the number of distinct roots that such a polynomial could have over Z/nZ, and show with an example that your estimate is indeed best possible. (I.e., describe a judicious choice of f having the maximal number of distinct roots.)

7. Write down the powers of x in the ring Z/2Z[x]/(x^{3} + x + 1) and show that every non-zero element in this ring can be expressed as a power of x.

8. Let p be a prime and let F denote the field Z/pZ with p elements. Let g(x) be a polynomial in F [x]. Show that gcd(x^{p} − x, g(x)) is a polynomial whose degree is equal to the number of distinct roots of g(x) in F.

9. Use the result of question 8 to show that the polynomial x^{2} + 1 has no roots in Z/pZ when p is a prime of the form 3 + 4m. (Note how this result compares with what you’ve found in Problem 4.)

10. Use the result of question 8 to describe a realistic algorithm for computing the number of roots of a polynomial g(x) in F = Z/pZ. (By realistic, we mean that a computer could perform the calculation in a matter of seconds, for p a prime of around 20 or 30 digits and g a polynomial of degree 10 or so.)