\documentclass[11pt]{article}
\usepackage{amsmath}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\lam}{\lambda}
\newcommand{\gam}{\gamma}
\newcommand{\ol}{\overline}
\newcommand{\noi}{\noindent}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\beq}{\begin{quote}}
\newcommand{\enq}{\end{quote}}
\newcommand{\hsone}{\hspace*{1cm}}
\newcommand{\hstwo}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Algebra V63.0344 \\ Assignment 2} \\ Solutions
\end{center}
\ben
\item In $Z_7[x]$ let $f(x)=2x^5+3x^4+4x+4$ and $g(x)=3x^2+x+5$. Find
$q(x),r(x)$ with $f(x)=q(x)g(x)+r(x)$ and either $r(x)=0$ or $r(x)$ having
smaller degree than $g(x)$.
\So Here is the division, writing $xi$ for $x^i$
\begin{verbatim}
3x3 + 2x + 4
3x2 + 1x + 5 2x5 + 3x4 + 0x3 + 0x2 + 4x + 4
2x5 + 3x4 + 1x3
6x3 + 0x2 + 4x
6x3 + 2x2 + 3x
5x2 + x + 4
5x2 + 4x + 6
4x + 5
\end{verbatim}
so $q(x)=3x^3+2x+4$ and $r(x)=4x+5$. (You may have learned division of
polynomials slightly differently, but if you got the same answer you
are OK.)
\item (*) What is the remainder when $x^{1000000}$ is divided by $x^3+x+1$
in $Z_2[x]$. (There is a pattern!)
\So One approach is to consider the remainder when $x^i$ is divided by $x^3+x+1$.
Starting at $i=0$ this goes $1,x,x^2,x+1,x^2+x, x^2+x+1, x^2+1$ and then starts
repeating. Each term may be found from the previous term by multiplying by $x$
and then dividing by $x^3+x+1$. So $x^7$ gives $1$ which means, as
$1000000=7(142857)+1$, that $x^{1000000}$ gives the same as $x^1$ which is $x$.
\item Further problems on $Z[\omega]$, as in assignment 1.
\ben
\item What are the possible values of $|\ah|^2$, $\ah\in Z[\omega]$,
with $|\ah|^2\leq 11$. (Notation: For $\ah=a+bi\in C$, $|\ah|=\sqrt{a^2+b^2}$,
the distance from $\ah$ to the origin on the complex plane.)
\So Eyeballing it is fine, here is an organized approach that would allow
computer calculation for much higher values than $11$.
Looking at the possible positions of $\ah= i+j\omega$ we see that the $y$-coordinate
is $j\frac{\sqrt{3}}{2}$ and the $x$ coordinate is $\frac{i}{2}+j$. The horozontal
lines are of two types. When $j$ is even the $x$ coordinates range over the integers
and when $j$ is odd the $x$ coordinates range over the half-integers, that is,
$\pm\frac{1}{2},\pm\frac{3}{2},\pm\frac{5}{2},\ldots$. That is, with $j=2k$ we
points $s+k\sqrt{3}i$ which have $|\ah|^2= s^2+3k^2$. For $j=(2k+1)$ we have
points $(s+\frac{1}{2})+ (k+\frac{1}{2})\sqrt{3}i$ which have
$|\ah|^2=[3(2k+1)^2+(2s+1)^2]/4$. From the symmetry (which can also be seen
geometrically) we need only look at $s,k\geq 0$. Lets consider each $j$
separately and take $s=0,1,\ldots$ until the value exceeds $11$. For $j=0$
we get (as values for $|\ah|^2$) $s^2=0,1,4,9$; for $j=2$,
$s^2+3=3,4,7$, for $j=1$, $[3+(2s+1)^2]/4=1,3,7$, for $j=3$,
$[27+(2s+1)^2]/4=7$ and for $j\geq 4$ we always have $|\ah|^2\geq 12$.
So the values are $0,1,3,4,7,9$.
\item Factor the numbers $2,3,4,5,6,7,8,9,10,11$ into irreducibles in
$Z[\omega]$. Prove that you do indeed have irreducibles. [One aid: If
$\ah=\beta\gam$ then $|\ah|^2=|\beta|^2|\gam|^2$. Also, $|\ah|^2=1$
exactly for the six units of assignment 1.]
\So By Unique Factorization the order in which we factor doesn't
matter so we first factor into integer primes and then the question
is the factorization of $2,3,5,7,11$ in $Z[\omega]$. Let $p$ be
an integer prime and suppose $p=\beta\gam$ in $Z[\omega]$. Then
$p^2=|p|^2=|\beta|^2|\gam|^2$. For the factorization to be nontrivial
[that is, not a unit times something] we must have $|\beta|^2=|\gamma|^2=p$.
From the previous problem this rules out $p=2,5,11$ so these $p$ are
primes in $Z[\omega]$. Conversely, where some $|\ah|^2=p$ we have
a factorization $p=\ah\ol{\ah}$ in $Z[\omega]$. Taking $\ah=2\omega+1=i\sqrt{3}$,
\[ 3 = |2\omega+1|^2= (2\omega+1)(2\ol{\omega}+1)=(2\omega+1)(-2\omega-1)= -(2\omega+1)^2 \]
Taking $\ah=2\omega+3=i\sqrt{3}+2$ we have
\[ 7 = (2\omega+3)(2\ol{\omega}+3) = (2\omega+3)(-2\omega+1) \]
Are these factors of $3,7$ now prime in $Z[\omega]$? Well, if $|\ah|^2$ is an integer prime
then $\ah$ must be a prime in $Z[\omega]$ (for $\ah=\beta\gam$ would imply that either
$|\beta|^2=1$ or $|\gam^2|=1$ which would mean they were units. These factors have square
absolute values $3,7$ so they are prime. Here is the final list
\ben
\item $2$ prime
\item $3=(-1)(2\omega+1)^2$
\item $4=2\cdot 2$
\item $5$ prime
\item $6=2\cdot 3 = (-1)2\cdot (2\omega+1)^2$
\item $7=(2\omega+3)(-2\omega+1)$
\item $8=2\cdot 2 \cdot 2$
\item $9=3\cdot 3 = (2\omega+1)^4$
\item $10=2\cdot 5$
\item $11$ prime
\een
\item Find the minimal positive real $x$ with the following property:
For {\em any} $\beta\in C$ there exists $\ah=a+b\omega\in Z[\omega]$
with $|\beta-\ah|\leq x$. (One approach: use the geometry of $Z[\omega]$.)
\So $Z[\omega]$ splits the plane into equilateral triangles of unit side.
The center of such a triangle is at distance $\frac{\sqrt{3}}{3}$ from
all three vertices and any other point is closer to one of them so the
minimal $x$ is $\frac{\sqrt{3}}{3}$.
\item Use the above and following the argument for $Z[i]$, prove that
$Z[\omega]$ is a Euclidean Ring under $d(\ah)=|\ah|^2$.
\So First, $d(\ah)=|\ah|^2$ so it must be positive for $\ah\neq 0$
and some calculation gives $d(a+b\omega)=a^2+b^2-ab$ so it is indeed
a positive integer. As $|\ah\beta|=|\ah|\cdot |\beta|$ for any complex
$\ah,\beta$, $d(\ah\beta)=d(\ah)d(\beta)\geq d(\ah)$ when $\ah,\beta\in
Z[\omega]-\{0\}$.
\par Now for the division. Given $\ah,\beta\in Z[\omega]$ with $\beta\neq 0$
set $\gam=\ah/\beta$. From the above problem there is a $q\in Z[\omega]$
with $|q-\gam| \leq \frac{\sqrt{3}}{3}$. Take this $q$ so that
\[ r= \ah-q\beta =
(\ah-q\beta) - (\ah-\gam\beta) = (\gam-q)\beta \]
so that
\[ |r| \leq |\gam-q||\beta| \leq \frac{\sqrt{3}}{3}\cdot|\beta| \]
and, squaring both sides,
\[ d(r) \leq d(\beta)/3 < d(\beta) \]
\een
\item More problems on $Z[\omega]$.
\ben
\item In the picture of $Z[\omega]$ (from assignment 1, you can get
the solutions) mark (with a little circle) those points which are
in the ideal $(2)$.
\item Describe $Z[\omega]/(2)$ as $\ol{\ah_1},\ldots,\ol{\ah_r}$ for
some specific $\ah_1,\ldots,\ah_r$. (You have to figure out what $r$
is!)
\So Effectively we are going two in each axis -- where the axes are
the X-axis and the 120 degree axis through $\omega$. We can take
$\ol{0},\ol{1},\ol{\omega},\ol{1+\omega}$ as the descriptions of
the cosets.
\item Give the multiplication table for $Z[\omega]/(2)$. Is it a
field? (It is automoatically a ring so to be a field every element
has to have a multiplicative inverse.)
\So $\ol{0}$ times anything is $\ol{0}$, and $\ol{1}$ is the multiplicative
identity.
\[ \ol{\omega}\ol{\omega} = \ol{\omega^2} = \ol{-1-\omega} =
\ol{1+\omega} \]
\[ \ol{\omega}\ol{1+\omega} = \ol{\omega+\omega^2} = \ol{-1} =
\ol{1} \]
\[ \ol{1+\omega}\ol{1+\omega} = \ol{1+2\omega+\omega^2}= \ol{\omega} \]
This is a field as $\ol{\omega}$ and $\ol{1+\omega}$ are inverses of
each other and $\ol{1}$ is the inverse of itself. It is a field with
four elements.
\een
\item Even more problems on $Z[\omega]$, as in assignment 1.
\ben
\item In the picture of $Z[\omega]$ (you can use the picture from
the solutions to assignment one)
mark (with a little circle) those points which are
in the ideal $(2)$.
\So Click on picture file
\item Describe $Z[\omega]/(2)$ as $\ol{\ah_1},\ldots,\ol{\ah_r}$ for
some specific $\ah_1,\ldots,\ah_r$. (You have to figure out what $r$
is!)
\So Since $2$ and $2\omega$ are in $(2)$ from any $a+b\omega$
we can subtract off the ``even part" leaving us with $a,b$ being
zero or one. So one set of representatives is $\ol{0}$, $\ol{1}$,
$\ol{\omega}$, $\ol{\omega + 1}$.
\item Give the multiplication table for $Z[\omega]/(2)$. Is it a
field? (It is automatically a ring so to be a field every element
has to have a multiplicative inverse.)
\So $\ol{0}$ times anything is $\ol{0}$ and $\ol{1}$ is a multiplicative
identity. $\ol{\omega}\cdot \ol{\omega}= \ol{\omega^2}$ and
$\omega^2=-1-\omega$ which reduces to $1+\omega$. That is,
$\ol{\omega}\ol{\omega}=\ol{1+\omega}$. As $\omega(1+\omega) =
-1$, $\ol{\omega}\ol{1+\omega}=\ol{1}$. Finally as
$(1+\omega)^2 = \omega$, $\ol{1+\omega}\ol{1+\omega}=\ol{\omega}$.
All nonzero elements have inverses so, yes, it is a field.
\een
\item Lets call an integral Domain $D$ together with a function
$d: D-\{0\}\ra \{0,1,2,\ldots\}$ a Banana Domain (not its real
name!) if
\ben
\item $d(\ah)\leq d(\ah\beta)$ for all nonzero $\ah,\beta\in D$
\item If $\ah,\beta\in D-\{0\}$ and if there does not exist $q\in D$
with $\ah=q\beta$ {\em then} there exist $a,b\in D$ with $a\ah+b\beta\neq 0$
and (critically!) $d(a\ah+b\beta)< d(\beta)$.
\een
Prove that a Banana Domain is a P.I.D. . (Hint: Follow
the argument that a Euclidean Domain is a P.I.D.)
\So Let $I\subset D$ be an ideal. If $I$ has only the element
$0$ then trivially $I=(0)$ is principle. Otherwise let
$\beta\in I$ be an element with minimal $d(\beta)$. As $I$
is closed under taking multiples, $(\beta)\subset I$. Now
let $\ah\in I$. Either there exists $q\in D$ with $\ah=q\beta$
(we say $\beta$ divides $\ah$ in this case) or there doesn't.
In the first case $\ah\in (\beta)$. In the second case we find
$a,b\in D$ given by the Banana property and set $\gam = a\ah+b\beta$.
As $a,b\in I$, $\gam\in I$. But $\gam\neq 0$ (from the property) and
this is impossible as $\beta$ was an element of $I$ with minimal
$d(\beta)$.
\een
\end{document}