[McGill] [Math.Mcgill] [Back]

189-235A: Algebra 1

Assignment 5

Week of October 19-23






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 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]$.


5. In class, we showed that a polynomial of degree $d$ with coefficients in a field $F$ has at most $d$ roots. Show by an examples that this statement ceases to be true when $F$ is replaced by an arbitrary ring, such as 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]$. 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 $\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.)


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 = \mathbb Z/p\mathbb Z$. (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.)