\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}