\documentstyle[12pt]{report}
\newcommand{\sk}{\vskip 0.2in}
\begin{document}
\begin{center}
{\Huge 189-235A: Basic Algebra I} \\ \sk
{\Huge Solutions for the Midterm Exam} \\ \sk
\end{center}
\def\Z{{\bf Z}}
\def\C{{\bf C}}
\def\R{{\bf R}}
\sk
\noindent
1. Let $(u_n)_{n\ge 0}$ be the sequence of real numbers defined recursively
by the rule
$$ u_0 = 0, \quad u_{n+1} = 2 u_n + 1. $$
Show that $u_n = 2^n-1$ for all $n\ge 0$.
\noindent
{\em This question was a straight application of induction. Most
of you were able to do it correctly.}
\sk
\noindent
2. Compute the greatest common divisor of $121$ and $77$ and express the result
as a linear combination of $121$ and $77$.
\noindent
{\em Apply the gcd algorithm as explained in class; one finds this
greatest common divisor is
$11 = 2\cdot 121 - 3\cdot 77.$}
\sk\noindent
3. Solve the congruence equation
$6x\equiv 10 \pmod{14}.$
\noindent
{\em There are {\bf two} distinct solutions to this equation in
$\Z_{14}$, namely $x=4$ and $x=11$. Most people who lost points on this
one did so by only listing one of the solutions. }
\sk \noindent
4. Show that if $p\in \Z$ is a prime, then the ring $\Z_p$ of congruence
classes modulo $p$ is a field.
\noindent
{\em This proof was done in class: given $[a]\ne 0$ in $\Z_p$,
one may consider the ${\rm gcd}$ of the integers $a$ and
$p$. This gcd divides $p$, so it is either $1$ or $p$; but it can't be
$p$ since $a$ is not divisible by $p$ (because $[a]\ne 0$) so
$\gcd(a,p)=1$. Now, writing the $\gcd$ as a linear combination
of $a$ and $p$, we get $1=au+pv$ for some integers $u$ and $v$.
The corresponding equation in $\Z_p$ becomes $[1] = [a][u]$.
Hence $[a]$ is invertible in $\Z_p$, therefore $\Z_p$ is a field.
}
\sk\noindent
5. Give an example of two finite rings $R_1$ and
$R_2$ which have the same cardinality but are not
isomorphic. (You should justify your assertion.)
\noindent
{\em There were two possible solutions here that I came across most often.
The first was to take a prime $p$ and consider the rings $R_1=\Z_p\times\Z_p$,
and the ring $R_2=\Z_{p^2}$. These rings are non-isomorphic, because (for example)
$R_2$ contains a non-zero solution of the equation $x^2=0$, namely,
$[p]$, while $R_1$ does not---yet an isomorphism from $R_2$ to $R_1$ would have to
carry a solution to such an equation to a solution of the corresponding
equation in $R_1$. One could also reason on the number of
solutions to the equation $px=0$ (there are $p^2$ such solutions in $R_1$,
and only $p$ in $R_2$) or of the equation $x^2=1$ (which has four solutions
in $R_1$, and only two solutions in $R_2$.)
A second solution was to take $R_1=M_2(\Z_n)$, and $R_2=\Z_n\times\Z_n\times\Z_n\times\Z_n$, for $n$ and integer $>1$.
The most immediate way to see that these two rings are not isomorphic
is to note that the matrix ring $R_1$ is not commutative, while
$R_2$ is.
Now that we've seen more about quotient rings, one could also take
as a third possible solution, $R_1$ to be one of the ``new" finite fields
that we saw in class, having $4$ or $8$ or $p^2$ elements, say,
and take $R_2$ to be any ring of the same cardinality that is not a field.
I leave you to work out the details... }
\sk\noindent
6. Show that the ring $\C$ of
complex numbers is {\em not} isomorphic to the Cartesian product $\R\times\R$
of the real numbers with itself.
{\em Alot of people lost points on this question by writing down the first
bijection $f$ from $\C$ to $\R\times\R$ that came to mind---typically this was
$f(a+bi)=(a,b)$---and showing that this function is not a homomorphism
because it does not respect the multiplication on $\C$.
This is not enough of course (how do you know that $f(a+bi)=(b,a)$,
or $f(a+bi) = (a+17b,3a-187 b)$, or any of another myriad functions
you could write down, might not be an isomorphism?
The key to the solution was to reason as in the previous problem, by
finding a ring-theoretic feature of $\C$ that is not shared
by $\R\times\R$.
There are various ways to do this, here are a few:
(1) by noting that every non-zero element of
$\C$ is invertible, so that $\C$ is a field, while the same is
not true of $\R\times\R$ (try inverting $(0,1)$, or $(1,0)$!);
(2) focussing on the equation $x^2+1=0$, which has two solutions
in $\C$, but none in $\R\times\R$; (3) by noting that
$\R\times\R$ has (infinitely many) zero divisors,
while $\C$ has none; (4) by noting that the equation
$x^2-1$ has two solutions in $\C$, but $4$ solutions in $\R\times\R$;
and so on and so forth. }
\sk\noindent
{\bf The next two problems are Bonus Questions}
\sk\noindent
7.
Let $f$ be a polynomial in $\Z[x]$ of degree $d$
and let $p\in \Z$ be a prime number.
Show that the set
$$ S = \{ n\in \Z \mbox { such that } p \mbox{ divides } f(n) \}$$
is the union of at most $d$ congruence classes modulo $p$.
\noindent
{\em Mea culpa! There was a mistake in the wording of this
question, which I corrected
during the writing of the exam. Of course one had to assume that $f$ is not
divisible by $p$, so that the natural image $\bar f$ of $f$
in the ring $\Z_p[x]$ is a non-zero polynomial; its degree, of course,
is then $\ge 0$ and less than or equal to $d$. Therefore $\bar f$ has at most
$d$ roots in $\Z_p$, since $\Z_p$ is a field. (Here is where we use the serious
theorem, that a non-zero polynomial of degree $d$
with coefficients in a field $F$ has at most
$d$ roots in $F$.)
Each of the roots of $\bar f$ is a congruence class modulo
$p$, and the set $S$ is (by definition) the union of these classes, of which
there are at most $d$. }
\sk\noindent
8. Let $p = 2m+1$ be an odd prime.
Show that
$$ 1^1 \cdot 2^2 \cdot 3^3 \cdots (p-1)^{p-1}
\equiv (-1)^{[m/2]} m! \pmod{p}.$$
\noindent
{\em The idea is to write the expression on the left---a product
of $2m$ terms,
viewed as an element in $\Z_p$---by grouping together
the $j$-th and the $(p-j)$-th term.
Together they give a contribution
to the product of
$$ j^j (p-j)^{p-j} = j^j (-j)^{p-j} = (-1)^{p-j} j^p = - (-1)^j j,$$
where we've used Fermat's Little theorem to get the last equality.
Hence our expression is equal to the
product of the terms
$ - (-1)^j j$, as $j=1,2,\ldots, m$.
The product of signs gives $(-1)^{[m/2]}$, and the product of the $j$'s from
$1$ to $m$ is of course just $m!$ ($m$-factorial). }
\end{document}