189-245A: Algebra 1

Assignment 3

Due: Monday, October 13.

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 $\mathbb Q[x]$. Write this greatest common divisor as a linear combination of $f(x)$ and $g(x)$ with coefficients in $\mathbb 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 ${\mathbb Z}/2\mathbb Z[x]$.

3. List all of the irreducible polynomials of degree $4$ in $\mathbb Z/2\mathbb Z[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 $\mathbb Z/p\mathbb Z$ of the polynomial $x^2+1$ in $\mathbb Z/p\mathbb Z[x]$. Use PARI-GP to compute this value for $p=29$ and $p=101$.

5. In class, we showed that a polynomial of degree $d$ with coefficients in a field $F$ has at most $d$ roots. Give an example to show that this statement ceases to be true when $F$ is replaced by a more general ring, namely, the ring $\mathbb Z/n\mathbb Z$ of residue classes modulo $n$ with $n$ a composite integer.

6. Let $d$ be a fixed integer. Let $n=pq\in \mathbb Z$ be an integer which is a product of two distinct primes, $p$ and $q$, and let $f\in \mathbb Z/n\mathbb Z[x]$ be a monic polynomial with coefficients in $\mathbb Z/n\mathbb Z$ 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 $\mathbb Z/n\mathbb Z$, 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 $\mathbb Z/2\mathbb Z[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 $\mathbb Z/p\mathbb Z$ with $p$ elements. Let $g(x)$ be a polynomial in $F[x]$. It was explaind in class 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$. Use this result to show that the polynomial $x^2+1$ has no roots in $\mathbb Z/p\mathbb Z$ when $p$ is a prime of the form $3+4m$. (Note how this result compares with what you've found in Problem 4.)

9. Let $p=1+2k$ be an odd prime.

(a) Show that the polynomials $A(x):= x^k-1$ and $B(x):= x^k+1$ each factor completely into distinct linear factors in $\mathbb Z/p\mathbb Z[x]$, whose roots are the non-zero squares and non-squares in $\mathbb Z/p\mathbb Z$.

(b) For $j\in \mathbb Z/p\mathbb Z$, describe the zeroes of the polynomials $$A_j(x):= A(x-j), \qquad B_j(x) := B(x-j).$$

(c) Use your work to describe an efficient probabilistic algorithm for calculating the roots of a polynomial $g(x)$ over $F = \mathbb Z/p\mathbb Z$.

10. Let $p$ be a prime number. Show that the polynomial $$f(x) = x^{p-1} + x^{p-2} + \cdots + x + 1,$$ whose roots are all the primitive $p$-th roots of unity, since $$ x^p-1 = (x-1) f(x),$$ is irreducible in $\mathbb Q[x]$. (Hint: make the change of variables $x = y+1$ in the polynomial $x^p-1$.)