\documentstyle[12pt]{report}
\newcommand{\sk}{\vskip 0.2in}
\newcommand{\lra}{\longrightarrow}
\newcommand{\R}{{\bf R}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\C}{{\bf C}}
\newcommand{\Q}{{\bf Q}}
\begin{document}
\begin{center}
{\Huge 189-235A: Basic Algebra I} \\ \vskip 0.1in
{\Huge Assignment 3} \\ \vskip 0.1in
{\Large Due: Monday, October 29 }
\end{center}
\sk
\noindent
1. Perform the division algorithm
for dividing $f(x) = 3x^4-2x^3+6x^2-x+2$ by $g(x) = x^2+x+1$ in
$\Q[x]$.
(I.e.,
find polynomials $q(x)$ and
$r(x)$ with ${\rm deg}(r)<{\rm deg}(g)$ satisfying
$f = gq + r.$
\sk\noindent
2. Same question as 1, with
$f(x) = x^5-x+1$ and $g(x) = x^2+x+1$ in ${\bf Z}/2\Z[x]$.
\sk\noindent
3. Let $f:\Z[x]\rightarrow \Z$ be the function which
to any polynomial $p(x)=a_0+a_1 x + \cdots + a_d x^d$
associates its constant term $a_0$:
$f(p) = a_0$.
Show that $f$ is a homomorphism of rings, i.e., it satisfies
$f(p_1+p_2) = f(p_1) + f(p_2)$ and $f(p_1 p_2) = f(p_1) f(p_2)$.
\sk\noindent
4. Find the gcd of
$x^4+3x^3- 2 x + 4$ and $x^2+1$ in ${\bf Z}/5\Z[x]$ using the
Euclidean algorithm.
\sk\noindent
5. List all the monic irreducible polynomials of degree $3$ in
$\Z/2\Z[x]$.
\sk\noindent
6.
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/p\Z$ of the polynomial
$x^2+1$ in $\Z/p\Z[x]$.
Show that there is no such root when $p$ is a prime of the form $3+4m$.
\sk\noindent
7. Make a list of all the primes $p\le 50$ for which the polynomial $x^2+x+1$ has a
root in $\Z/p\Z[x]$, and those primes for which it remains irreducible.
Can you detect a pattern, similar to the one in problem 6?
\sk\noindent
8. Find a polynomial of degree $2$ in $\Z/6\Z[x]$ that has four roots in
$\Z/6\Z$. Why does this not contradict the theorem shown in class that
a polynomial in $F[x]$ of degree $d$ has at most $d$ roots?
\sk\noindent
9. Exercise (2), parts (a), (c), (e) and (f) on page 65
of Eyal Goren's notes.
\sk\noindent
10. Let $p$ be a prime and let $F$ denote the field $\Z/p\Z$ with $p$
elements.
(a) Show that the polynomial $x^p-x$ factors into $p$ distinct linear factors
in $F[x]$.
(b) 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$.
(c) Use (b) to describe a realistic algorithm for computing the number of roots
of a polynomial $g(x)$ in $F$. (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.)
\end{document}