\documentclass[11pt,a4paper,twoside]{article}
\usepackage{amsmath,amssymb,amsthm}
%\usepackage{mathrsfs}
\usepackage{paralist}
\usepackage{verbatim}

\newtheorem{problem}{Problem}
\theoremstyle{definition}
\newtheorem*{solution}{Solution}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{(\theenumii)}
\renewcommand{\theequation}{\fnsymbol{equation}}
\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\renewcommand{\emptyset}{\varnothing}

\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\divides}{\mid}

\usepackage{bm}
%\newcommand{\sv}[1]{\bm{#1}}
\begin{document}
\title{Exam 1 solutions}
\author{Math 116: Finashin, Pamuk, Pierce, Solak}
\date{Thursday, April 7, 2011}
\maketitle

\begin{problem} (15 pts)
  \begin{enumerate}
  \item 
Find the greatest common divisor $d$ of $453$ and $213$.
Present $d$ in the form $d=453x+213y$.
\item
If there is one, find a solution to $213x\equiv12\pmod{453}$.
\item
Find the least positive integer in $\{4530x+2139y\colon x,y\in \Z\}$. 
  \end{enumerate}
\end{problem}

\begin{solution}
  \begin{enumerate}
  \item 
First apply the Euclidean algorithm:
    \begin{align*}
      453&=213\cdot2+27,\\
213&=27\cdot7+24,\\
27&=24\cdot1+3,\\
24&=3\cdot 8.
    \end{align*}
So $\gcd(453,213)=3$.  Also
 we compute
\begin{align*}
  3&=27-24\\
&=27-(213-27\cdot7)\\
&=27\cdot8-213\\
&=(453-213\cdot2)\cdot8-213\\
&=453\cdot8-213\cdot17.
\end{align*}
\item
By (a), we have $3\equiv213\cdot-17\pmod{453}$, so
\begin{equation*}
213x\equiv12
\iff 213x\equiv4\cdot3\equiv213\cdot-68.
\end{equation*}
Therefore the congruence is solved when $x\equiv-68\equiv385\pmod{453}$.
\item
$4530x+2130y=10(453x+213y)$, so the least positive integer in the given set
  is $10\cdot3$, or \fbox{$30$}.
  \end{enumerate}
\end{solution}

\begin{remark}
\begin{asparaenum}[1.]
\item
There is a reason why the three parts of this problem are together.
One application of the Euclidean algorithm is enough to give the
answers of all three parts.  (Some people used the algorithm two or
three times; this was unnecessary.) 
\item
The second half of part (a) does not ask you to write ``$3=453x+213y$''
and then stop; it asks for a solution to this equation. 
\item
In part (b), one may observe that $3$ divides each of $213$, $12$, and
$453$, so that 
\begin{equation*}
213x\equiv12\pmod{453}
\iff 71x\equiv4\pmod{151}.
\end{equation*}
From part (a) we have $1=151\cdot8+71\cdot-17$, so the congruence is solved by
\begin{gather*}
x\equiv4\cdot-17\equiv-68\equiv83\pmod{151},\\
x\equiv83,234,385\pmod{453}.	
\end{gather*}
This is the complete solution, but it was not required to find this:
the problem asked just for \emph{one} solution. 
\item
In part (c), some people seemed to confuse the \emph{least} positive
integer in the given set with the \emph{least} common multiple of
$4530$ and $2130$. 
\item
Part (c) does not ask for the values of $x$ and $y$ such that
$4530x+2130y$ is minimized among positive integers; it asks
for the minimum possible positive value of this expression. 
\end{asparaenum}
\end{remark}


\begin{problem}(8pts)
Let $G$ be the set of even integers and $*$ be the binary operation on $G$ defined by $x*y=x+y+4$. Determine whether $(G,*)$ is a group or not. Prove your claim.
\end{problem}


\begin{solution}
Since $x$, $y$, are $4$ are even, their sum is also even; so $G$ is closed under $*$.
To simplify some computations, we may note also that, since $+$ is commutative, so is $*$.
Let us check for an identity. We claim that $-4$ is an identity with respect to $*$.  Indeed,
\begin{equation*}
x*(-4)=x-4+4=x
\end{equation*}
(and therefore also $(-4)*x=x$, by commutativity of $*$).  So $-4$ is an identity.
Considering
\begin{align*}
x*(y*z)
&=x*(y+z+4)\\
&=x+(y+z+4)+4\\
&=(x+y+4)+z+4\\
&=(x+y+4)*z\\
&=(x*y)*z, 
\end{align*}
we have that $*$ is associative.
Now check for inverses.  We claim that $-x-8$ is the inverse of $x$ with respect to $*$.
We have 
\begin{equation*}
x*(-x-8)=x-x-8+4=-4
\end{equation*}
(hence also $(-x-8)*x=-4$).
Therefore $(G,*)$ is a group. 
\end{solution}


\begin{problem}(7pts)
Let $a*b=a+b+3ab$ , does $*$ define a binary operation on
the set $\Q_+$ of positive rationals ?  Is $*$ associative? Explain.
\end{problem}


\begin{solution}
Since the sum and product of two positive rationals is again a positive rational, $\Q_+$ is closed under $*$.  Therefore $*$ is a binary operation on $\Q_+$.

For the associativity, we have
\begin{align*}
a*(b*c)
&=a*(b+c+3bc)\\
&=a+(b+c+3bc)+3a(b+c+3bc)\\
&=a+b+c+3bc+3ab+3ac+9abc.
\end{align*}
while
\begin{align*}
(a*b)*c
&=(a+b+3ab)*c\\
&=(a+b+3ab)+c+3(a+b+3ab)c\\
&=a+b+3ab+c+3ac+3bc+9abc.
\end{align*}
So we see that $a*(b*c)=(a*b)*c$. Hence $*$ is an associative binary operation on $\Q_+$.
\end{solution}



\begin{problem}(15pts)
Let $G$ be the group $(\Z_{28}, +)$.
\begin{enumerate}
\item
Find all generators of $G$.
\item
List all the subgroups of $G$.  For each subgroup, different from $G$, write down all its elements.
\end{enumerate}
\end{problem}

\begin{solution}
\begin{enumerate}
\item 
When $0\leq k<28$, we have $k=1,3,5,9,11,13,15,17,19,23,25,27$ if and only if
$\gcd(k,28)=1$.  Therefore the generators of $G$ are $[1]$, $[3]$,
 $[5]$, $[9]$, $[11]$, $[13]$, $[15]$, $[17]$, $[19]$, $[23]$, $[25]$,
$[27]$.

\item 
The subgroups of $G$ are $\langle[d]\rangle$, where $d\divides28$; so they are 
\begin{align*}
\langle[1]\rangle,& &\langle[2]\rangle,& &\langle[4]\rangle,& &\langle[7]\rangle,& &\langle[14]\rangle,& &\langle[28]\rangle.
\end{align*}
Moreover,
\begin{align*}
\langle[1]\rangle &= \Z_{28}\\
\langle[2]\rangle &= \{[2], [4], [6], [8], [10], [12], [14], [16], [18], [20], [22], [24], [26], [0]\}\\
\langle[4]\rangle &= \{[4], [8], [12], [16], [20], [24], [0]\}\\
\langle[7]\rangle &= \{[0], [7], [14], [21]\}\\
\langle[14]\rangle &= \{[14], [0]\}\\
\langle[28]\rangle &=\langle[0]\rangle= \{[0]\}
\end{align*}
\end{enumerate}
\end{solution}

\clearpage

\begin{problem}(5pts)
Let $G$ be an abelian group and $H=\{g\in G | g^2=e \}$, where $e$ is the identity element of $G$. Show that $H$ is a subgroup of $G$.
\end{problem}


\begin{solution}
Since $e^2=ee=e$, we have $e\in H$: the identity is in $H$.

Let $a,b\in H$, so that $a^2=e$ and $b^2=e$.  To show that $H$ is closed under multiplication, consider $(ab)^2$.  Since $G$ is abelian, we have
\begin{equation*}
(ab)^2=abab=aabb=a^2b^2=ee=e, 
\end{equation*}
so $ab\in H$.  Thus $H$ is closed.

Let $a\in H$, so that $a^2=e$, and let $a^{-1}$ be the inverse of $a$. Consider
\begin{equation*}
a^{-1}a^{-1}=(a^{-1})^2=(a^2)^{-1}=e^{-1}=e,
\end{equation*}
 so $a^{-1}\in H$.

Therefore, $H$ is a subgroup of $G$.

\end{solution}



\begin{problem}(10pts)
\begin{enumerate}
\item Let $G$ be a group. For $a\in G$, define a mapping $t_a:G\longrightarrow G$ by $t_a(x)=axa^{-1}$ for all $x\in G$.  Prove that $t_a$ is an isomorphism.

\item i)Prove that $\Z_2$ is not isomorphic to $\Z_3$.\\
ii) Prove that $\Z_6$ is not isomorphic to $S_3$, where $S_3$ is  the group of permutations on the set $\{ 1,2,3\}$.
\end{enumerate}
\end{problem}


\begin{solution}
\begin{asparaenum}
\item
If $x,y\in G$, then 
\begin{equation*}
t_a(xy)=axya^{-1}=axa^{-1}aya^{-1}=t_a(x)\cdot t_a(y). 
\end{equation*}
So, $t_a$ is a homomorphism.
Now let $x,y\in G$ and $t_a(x)=t_a(y)$.  Then $axa^{-1}=aya^{-1}$.  Since $G$ is a group, it allows left and right cancellation.  Therefore $x=y$. So, $t_a$ is one-to-one.  Finally,
let $x\in G$.  We shall show that there is $y$ in $G$ such that $t_a(y)=x$.  Let $y=a^{-1}xa$.  Then
\begin{equation*}
t_a(y)=t_a(a^{-1}xa)=aa^{-1}xaa^{-1}=x.
\end{equation*}
So, $t_a(x)$ is onto.
Hence, $t_a(x)$ is an isomorphism.
\item
\begin{compactenum}[i)]
\item
Since their orders are different, $|\Z_2|=2\neq 3=|\Z_3|$, we cannot find a bijection between the sets, so the groups cannot be isomorphic.
\item
$\Z_6$ is an abelian group, but $S_3$ is not.  Under an isomorphism being abelian must be preserved: $\phi(xy)=\phi(yx)$ since $xy=yx$, so 
\begin{equation*}
\phi(x)\cdot\phi(y)=\phi(xy)=\phi(yx)=\phi(y)\cdot\phi(x).
\end{equation*} 
\end{compactenum}
\end{asparaenum}
\end{solution}

\begin{remark}
In the last part, it would be acceptable to note that $\Z_6$ is cyclic, but $S_3$ is not.
\end{remark}

\end{document}
