\documentclass[12pt,letterpaper]{amsart}
%\usepackage[utf8x]{inputenc}
%\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{float}


\usepackage{amssymb}
  \newtheorem{theorem}{Theorem}[section]
    \newtheorem{lemma}[theorem]{Lemma}
    \newtheorem{proposition}[theorem]{Proposition}
    \newtheorem{corollary}[theorem]{Corollary}
    \newtheorem{definition}[theorem]{Definition} 
    \newtheorem{claim}[theorem]{Claim}
    \newtheorem{example}[theorem]{Example} 
    \newtheorem{remark}[theorem]{Remark}

\newcommand{\Mod}{\operatorname{mod}}

 
\begin{document}
\title{Homework $\#$1}
\author{Due 9/25/13 at start of class }
\maketitle
\subsection*{Problem 1 (D$\&$F 0.3.3)} Recall that an integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$. In fact, the remainder of any positive integer after division by $9$ is the same as the sum of the digits modulo $9$. Prove this.

\noindent [Hint: let $a=a_n10^n+a_{n-1}10^{n-1}+\dots+a_110+a_0$ be any positive integer.]

\subsection*{Problem 2 (D$\&$F 0.3.11,12,13)} Consider the set $$(\mathbb{Z}/n\mathbb{Z})^\times=\{[a]\in \mathbb{Z}/n\mathbb{Z}\;\vert\; \exists [c]\in \mathbb{Z}/n\mathbb{Z}\; \text{with}\; [a][c]=[1]\}.$$ 
\begin{itemize}
\item[(a)] Prove that if $[a],[b]\in(\mathbb{Z}/n\mathbb{Z})^\times$, then so is $[a]*[b]$.
\item[(b)] Let $n\in\mathbb{Z}$, $n>1$ and let $a\in\mathbb{Z}$ with $1\leq a \leq n$. Prove that if $a$ and $n$ are not relatively prime, there exists an integer $b$ with $1\leq b<n$ such that $ab\equiv 0 (\Mod n)$ and deduce that there cannot be an integer $c$ such that $ac\equiv 1 (\Mod n)$.
\item[(c)] Let $n\in \mathbb{Z}$, $n>1$ and let $a\in\mathbb{Z}$ with $1\leq a\leq n$. Prove that if $a$ and $n$ are relatively prime then there is an integer $c$ such that $ac\equiv 1(\Mod n)$. 

\noindent [Hint: use the fact that the g.c.d of two integers is a $\mathbb{Z}$-linear combination of the integers: read Section 0.2.]

\item[(d)] Conclude Proposition 0.3.4 and that $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group under multiplication of congruence classes.
\end{itemize}


\subsection*{Problem 3 (D$\&$F 0.1.5)} Determine whether the following functions $f$ are well-defined:
\begin{itemize}
\item[(a)] $f:\mathbb{Q}\rightarrow\mathbb{Z}$ defined by $f(\frac{a}{b})=a$.
\item[(b)] $f:\mathbb{Q}\rightarrow\mathbb{Q}$ defined by $f(\frac{a}{b})=\frac{a^2}{b^2}$
\end{itemize}

\subsection*{Problem 4 (D$\&$F 0.1.7)}
Let $A$ and $B$ be sets and let $f$ be a map from $A$ to $B$. 
\begin{itemize}
\item[(a)] Prove that the relation 
$$a\sim b\;\text{if and only if}\; f(a)=f(b)$$
is an equivalence relation.
\item[(b)] Now suppose $f$ is a surjective map. Prove that the equivalence classes of the relation in (a) are the fibers of $f$.

\end{itemize}  
\subsection*{Problem 5 (D$\&$F 1.1.24)} Let $G$ be a group. If $a$ and $b$ are commuting elements of $G$ prove that $(ab)^n=a^nb^n$ for all $n\in\mathbb{Z}$.

\noindent [Hint: do this first for positive $n$.]

\subsection*{Problem 6 (D$\&$F 1.1.25)} Let $G$ be a group. Prove that if $x^2=1$ for all $x\in G$ then $G$ is abelian.

\subsection*{Problem 7 (D$\&$F 1.1.17)} Let $G$ be a group. Let $x$ be an element of $G$. Prove that if $\vert x\vert=n$ for some positive integer $n$ then $x^{-1}=x^{n-1}$.

\subsection*{Problem 8 (D$\&$F 1.1.32)} Let $G$ be a group. If $x$ is an element of finite order $n$ in $G$, prove that the elements $1,x,x^2,\dots x^{n-1}$ are all distinct. Deduce that $\vert x\vert \leq \vert G\vert$.

\subsection*{Challenge Problem} Use Problems 7 and 8 to prove the following:
If $G$ is a group of order $4$, then either $G$ has an element of order $4$ or every nonidentity element of $G$ has order $2$. 

 
\end{document}