\documentclass[12pt]{article}
\newcommand{\set}[1]{\lbrace #1 \rbrace}
\newcommand{\setc}[2]{\lbrace #1 \mid #2 \rbrace}
\usepackage{amssymb,amsfonts,amsmath}
\pagestyle{myheadings} \markright{Battaglino}
\newenvironment{hwproblem}[1]
{\noindent{\bf{Problem #1:}} }
{\vspace{0.2 in}}

\newenvironment{solution}
{\noindent{\underline{Solution:}} }
{\vspace{0.2 in}}

\begin{document}
\begin{center}
\Large
21-373: Algebraic Structures\\
Assignment 1
\end{center}

\begin{flushright}
Peter Battaglino\\ 19. January, 2005
\end{flushright}

\begin{hwproblem}{0.8}
Suppose $a$ and $b$ are integers that divide the integer $c$. If $a$ and $b$ are
relatively prime, show that $ab$ divides $c$. Show, by example, that if $a$ and $b$
are not relatively prime, then $ab$ need not divide $c$.
\end{hwproblem}

\begin{solution}
Let $c\in \mathbb{Z}$, and suppose $c>1$, without loss of generality (if $c$ is
negative, $-1$ will be one of the factors in its prime decomposition, and the
rest of them will be the prime factors of $-c$). Then by the fundamental theorem
of arithmetic, we can write
\begin{equation}
c = \prod_{i=1}^{C} c_i,
\end{equation}
where $C$ is the number of (not necessarily distinct) prime factors of $c$.
Since $a\mid c$, we know that some sub-product of the $c_i$'s must equal $a$. Similarly,
$b\mid c$ so another sub-product of the $c_i$'s must equal $b$. But, since $a$ and $b$
are relatively prime, we know that they do not have any prime factors in common, so
their product must also be a sub-product of the prime factors of $c$. Thus, $ab\mid c$.
Now we show by example that if $a$ and $b$ are not relatively prime, $ab$ need not
divide $c$. Let $a=4$, $b=6$, and $c=12$. It is obvious that $4\mid12$ and $6\mid 12$, but
24 does not divide 12.
\end{solution}
\clearpage
\begin{hwproblem}{0.12}
Let $a$ and $b$ be positive integers and let $d = \gcd(a,b)$ and $m = {\mathrm{lcm}}(a,b)$.
If $t$ divides both $a$ and $b$, prove that $t$ divides $d$. If $s$ is a multiple
of both $a$ and $b$, prove that $s$ is a multiple of $m$.
\end{hwproblem}

\begin{solution}
Let $a,b \in \mathbb{N} \setminus \set{0,1}$ (1 is a trivial case). By the fundamental theorem of
arithmetic, we can write $t=t_1\cdot t_2 \cdots t_T$ and $d=d_1\cdot d_2\cdots d_D$, where
each of the factors are prime. Since $d=\gcd(a,b)$ we can write
\begin{eqnarray}
a & = & d\cdot\tilde{a}_1\cdots\tilde{a}_A \\
b & = & d\cdot\tilde{b}_1\cdots\tilde{b}_B,
\end{eqnarray}
where, again, each of the $\setc{\tilde{a}_i}{i\in[1,A]\cap\mathbb{N}}$ are prime (similarly for $b$),
and all of the $\lbrace\tilde{a}_i\rbrace$ are relatively prime to the $\lbrace\tilde{b}_j\rbrace$.
Since $t\mid a$, $t$ must be a product of prime factors of $a$. But $t\mid b$, so $t$ must also be a product
of prime factors of $b$. Also, since by construction $\set{\tilde{a}_1,\cdots,\tilde{a}_A}
\cap\set{\tilde{b}_1,\cdots,\tilde{b}_B}=\emptyset$, we know that the prime factors
of $t$ must belong to the set of (not necessarily distinct) prime factors of $d$ in order for
$t\mid a$ and $t\mid b$ to hold. Since the prime factors of $d$ contain the collection of prime factors
of $t$, we know that $t\mid d$, which was to be shown.\\

\noindent Now let $s$ be a multiple of both $a$ and $b$. We wish to show that $s$ is also a multiple of $m$.
If $a$ and $b$ are relatively prime, the proof is trivial, since ${\mathrm{lcm}}(a,b)=ab$ in this
case, and $s$ would have to be a multiple of $ab$. So let us suppose that $a$ and $b$ have prime
factors in common. We can express this as
\begin{eqnarray}
a & = & c \tilde{a} \\
b & = & c \tilde{b},
\end{eqnarray}
with $c\in\mathbb{Z}$, where $\tilde{a}\in\mathbb{Z}=\tilde{a}_1 \cdot \tilde{a}_2 \cdots \tilde{a}_A$
is relatively prime to a similarly defined $\tilde{b}$. Then we see that
${\mathrm{lcm}}(a,b) = m = c\tilde{a}\tilde{b}$. Now, it is given that $s$ is a multiple of both
$a$ and $b$, which we can write as $s = pa = pc\tilde{a}$ and $s = qb = qc\tilde{b}$ for some
$p,q\in\mathbb{Z}$. But this implies that $p\tilde{a} = q\tilde{b}$, and since by definition
$\tilde{a}$ and $\tilde{b}$ have no common factors, we see that $p$ must be a multiple of $\tilde{b}$
and $q$ a multiple of $\tilde{a}$. Thus we have $s=pc\tilde{a}=k\tilde{b}c\tilde{a}=kc\tilde{a}\tilde{b}$
for some $k\in\mathbb{Z}$. But $c\tilde{a}\tilde{b}=m$, so we see that $s$ is a multiple of $m$, which
is what we set out to show.
\end{solution}
\clearpage
\begin{hwproblem}{2.12}
For any integer $n>2$, show that there are at least two elements in $U(n)$ that satisfy $x^2=1$.
\end{hwproblem}

\begin{solution}
We know that $1\in U(n)$ and $1^2=1$, for all $n>2$, so that's one element. There is a second
guaranteed element as well: $n-1$. To see this, we just take its square: $(n-1)(n-1)\mod n=
(n^2-2n+1)\mod n=1$. Now we just need to make sure that $n-1\in U(n)$, that is that $n-1$ and $n$
are relatively prime. A theorem in our text states that $a\in\mathbb{Z}$ has a multiplicative inverse
modulo $n$ iff $a$ and $n$ are relatively prime. We know that $n-1$ has a multiplicative inverse (itself),
so we also know that $n-1$ and $n$ are relatively prime. Thus, we know that $U(n)$ has at least two
elements whose square is the identity element, which is what we set out to show.
\end{solution}
\clearpage
\begin{hwproblem}{2.14}
Let $G$ be a group with the following property: If $a$, $b$, and $c$ belong to $G$ and $ab=ca$, then
$b=c$. Prove that $G$ is Abelian.
\end{hwproblem}

\begin{solution}
To prove this we simply multiply the equation $b=c$ on the right by $a$ to get $ba=ca$. So we
have the implication $ab=ca \Rightarrow ba=ca$, which implies that $ab=ba$ for all $a,b\in G$,
which is the definition of an Abelian group.
\end{solution}
\clearpage
\end{document}