\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim}
\usepackage{enumerate}
\usepackage{microtype}
\usepackage{url}
\usepackage[letterpaper]{geometry}

%\addtolength{\evensidemargin}{-.5in}
%\addtolength{\oddsidemargin}{-.5in}
%\addtolength{\textwidth}{0.8in}
%\addtolength{\textheight}{0.6in}
%\addtolength{\topmargin}{-.3in}

\newtheoremstyle{quest}{\topsep}{\topsep}{}{}{\bfseries}{}{ }{\thmname{#1}\thmnote{ #3}.}
\theoremstyle{quest}
\newtheorem*{definitionq}{Definition}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{challenge}[theorem]{Challenge Problem}

\title{\vspace{-50pt}Elementary Number Theory\\
\normalsize Math 175, Section 30, Autumn 2010\\
\large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\
Tom Church ({\tt tchurch@math.uchicago.edu})\\
\url{www.math.uchicago.edu/~tchurch/teaching/175/}}
\author{}
\date{}


\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\Zi}{\Z[i]}

% \DeclareMathOperator{\sin}{sin}   %% just an example (it's already defined)
\DeclareMathOperator{\norm}{norm}


\renewcommand{\baselinestretch}{1.2}
\begin{document}
\maketitle
\vspace{-35pt}
\begin{center}
{\huge \bf Homework 3}\\\vspace{15pt}
{\Large Due Tuesday, October 26 in class.}
\end{center}

Recall that $\Z[i]$ is the number system consisting of formal expressions of the form $a+bi$ where $a\in \Z$ and $b\in \Z$.\\

\begin{definitionq}[HW\!.3.1]
Given $x,y\in \Z[i]$ and $d\in \Z[i]$, we say that $d$ is \emph{a GCD of $x$ and $y$} if:
\begin{itemize}
\item $d|x$ and $d|y$, and\hfill [$d$ is a common divisor]
\item if $e|x$ and $e|y$, then $e|d$.\hfill [every common divisor divides $d$]
\end{itemize}
The reason we say ``\emph{a} GCD'' is that if $d$ is a GCD of $x$ and $y$, then so are $-d$, $id$, and $-id$. \phantom{x}\hfill [compare with Theorem~1.30]
\end{definitionq}
\begin{question}\ 
\begin{enumerate}[a)]
\item Let $a, b$ be nonzero elements of $\Z[i]$. If we apply the Division Algorithm sequentially:
\[
\begin{array}{rclll}
a &=& bq_1+r_1 & \phantom{MMM} & 0<N(r_1)<N(b) \\
b &=& r_1q_2+r_2 & & 0<N(r_2)<N(r_1) \\
r_1 &=& r_2q_3+r_3 & & 0<N(r_3)<N(r_2) \\
& \vdots & & & \\
r_{k-2} &=& r_{k-1}q_k+r_k & & 0<N(r_k)<N(r_{k-1}) \\
r_{k-1} &=& r_kq_{k+1} \\
\end{array}\]
then $r_k$ is a GCD of $a$ and $b$.\hfill [compare with Theorem~1.37]
\item Prove that if $d$ is a GCD of $x$ and $y$, then we can write $d=ax+by$ for some $a,b\in \Z[i]$.  \phantom{x}\hfill[compare with Theorem~1.31]
\end{enumerate}\vskip6pt

\begin{definitionq}[HW\!.3.2]
Given $x,y\in \Z[i]$, we say that $x$ and $y$ are relatively prime if $1$ is a GCD of $x$ and $y$.  \hfill [compare with Definition~1.34]
\end{definitionq}\vskip6pt

Recall that $x$ is \emph{associated} to $y$ if $x|y$ and $y|x$ (you proved this means $x=\pm y$ or $\pm iy$).
\begin{definitionq}[HW\!.3.3]
A nonzero element $x\in \Z[i]$ is called \emph{irreducible} if every divisor of $x$ is associated to $1$ or associated to $x$.\hfill [compare with Definition 2.1]
\end{definitionq}\vskip6pt

\begin{definitionq}[HW\!.3.4]
A nonzero element $x\in \Z[i]$ is called a \emph{unit} if it is associated to 1.
\end{definitionq}\vskip10pt

\begin{enumerate}[c)]
\item[c)] Let $x$ be an irreducible element of $\Z[i]$. Prove that if $x|ab$, then $x|a$ or $x|b$. (Hint: show that if $x\!\!\not|\,a$, then $x$ and $a$ are relatively prime.)\hfill [compare with Theorem 2.4]\vskip6pt
\item[d)] Prove that every nonzero element of $\Z[i]$ which is not a unit has at least one irreducible factor.\hfill [compare with Theorem 2.2]\vskip6pt
\item[e)] Prove that every nonzero element $a\in\Z[i]$ can be factored into a product of irreducible elements times a unit: $a=u\cdot x_1\cdots x_k$, where $u$  is a unit and each $x_i$ is irreducible.\linebreak
\phantom{x}\hfill [compare with Theorem 2.3]\vskip6pt
\item[f)] \textbf{Unique factorization in $\Z[i]$}. Prove that every nonzero element $a\in\Z[i]$ can be factored into a product of irreducibles in a unique way, up to units and the order of the factors.

In other words, if $a=u\cdot x_1\cdots x_k$ and $a=v\cdot y_1\cdots y_\ell$ are two factorizations of $a$ as in part e), then $k=\ell$ and there is a reordering of the factors so that $x_i$ is associated to $y_i$ for all $i=1,2,\ldots,k$. \hfill [compare with Theorem 2.5]
\end{enumerate}
\end{question}\newpage

\begin{question}
We define the number system $\Z[\sqrt{-5}]$ to be the collection of formal expressions of the form $a+b\sqrt{-5}$, where $a\in \Z$ and $b\in \Z$.
For example, $2+0\sqrt{-5}$, $3+2\sqrt{-5}$, and $-2+7\sqrt{-5}$ are all elements of $\Z[\sqrt{-5}]$.\\

If $x\in \Z[\sqrt{-5}]$ and $y\in\Z[\sqrt{-5}]$ are two elements of $\Z[\sqrt{-5}]$, we define addition and multiplication as follows:
\[\text{if }x=a+b\sqrt{-5}\quad\text{ and }\quad y=c+d\sqrt{-5}\text{, \ \ then }\qquad x+y=(a+c)+(b+d)\sqrt{-5}\]
\[\text{if }x=a+b\sqrt{-5}\quad\text{ and }\quad y=c+d\sqrt{-5}\text{, \ \ then }\qquad x\cdot y=(ac-5bd)+(ad+bc)\sqrt{-5}\]
These operations are commutative, associative, and distribute (they satisfy all the axioms up through Axiom D). The additive identity is $0=0+0\sqrt{-5}$, and the multiplicative identity is $1=1+0\sqrt{-5}$.\\[6pt]
\begin{enumerate}[a)]
\item Come up with a definition of a function $N\colon \Z[\sqrt{-5}]\to \Z$ with the following properties.
\begin{enumerate}[I.]
\item $N(0)=0$
\item $N(1)=1$ and $N(-1)=1$
\item $N(x)\neq 1$ for some nonzero $x$\hfill (just to rule out silly answers)
\item $N(x\cdot y)=N(x)\cdot N(y)$ for any $x,y\in \Z[\sqrt{-5}]$\hfill(this is the important condition)
\end{enumerate}
\item One way to factor $6=6+0\sqrt{-5}$ into irreducibles is
\[6=2\cdot 3.\]
Find a \underline{different} way to factor $6$ as a product of irreducibles,\footnote{Writing it as $6=(-2)(-3)$ does not count as ``different''.} showing that \emph{\textbf{we do not have unique factorization}} in $\Z[\sqrt{-5}]$. 

\end{enumerate}
\end{question}
\end{document}