\documentclass[11pt]{article} % Define the document type. The 11pt refers to font size.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Include packages required to compile document:

\usepackage{amssymb, amsthm, amsmath} % These packages are used for the basic math symbols and environments.
\usepackage{enumerate} % This package is used to provide various types of numbering for lists.
\usepackage[margin=1.25in]{geometry} % This is to set wide margins, so there is room to leave comments
\usepackage[parfill]{parskip} % This provides formatting for paragraphs so that there are no indents and paragraphs are separated by a line skip.
\usepackage[pdftex,colorlinks=true,urlcolor=blue]{hyperref}
% You may need to add additional packages depending on the commands you want to use.

%%%%%%%%%%%%%%%%%%%%
% User defined commands:

\newcommand{\br}{\mathbb R} % this is the symbol for the real numbers.  mathbb is the "blackboard bold" font
\newcommand{\bz}{\mathbb Z} % integers
\newcommand{\bq}{\mathbb Q} % rationals
\newcommand{\bn}{\mathbb N} % natural numbers

\newcommand{\co}{\colon\thinspace} % this is a good way to write functions, i.e instead of $f: X \to Y$, you would write $f\co X \to Y$.  It looks nicer.

% You may add shortcuts for any commands you find yourself using frequently.  

\DeclareMathOperator{\ord}{ord} % This command lets you declare math operators.  Some built in operators are \sin for sine and \cos for cosine.  This makes the operators appear nicely in the math environment.  If I wanted to make the sine operator myself, it would look like \DeclareMathOperator{\sin}{sine}.  

\DeclareMathOperator{\lcm}{lcm} % least common multiple

% Ender user defined commands
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These establish different environments for stating Theorems, Lemmas, Remarks, etc.

\newtheorem{Thm}{Theorem}
\newtheorem{Prop}[Thm]{Proposition}
\newtheorem{Lem}[Thm]{Lemma}
\newtheorem{Cor}[Thm]{Corollary}

\theoremstyle{definition}
\newtheorem{Def}[Thm]{Definition}

\theoremstyle{remark}
\newtheorem{Rem}[Thm]{Remark}
\newtheorem{Ex}[Thm]{Example}

\theoremstyle{definition}
\newtheorem{Exercise}{Exercise}
\newtheorem{ExGraded}[Exercise]{*Exercise}
\newtheorem{ExChallenge}[Exercise]{**Exercise}

\newenvironment{Solution}{\noindent{\it Solution.}}{\qed}

%End environments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Now we're ready to start
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

% This is for the title
{\Large {\bf Homework 2}} \hfill MATH 301 \\
{Solutions to graded problem} \\[-2mm]
\line(1,0){470}

\bigskip



%\textbf{Reading.} Reach Chapter 1 in the course textbook (\emph{Abstract Algebra} by Thomas W. Judson.



\setcounter{Exercise}4


\begin{Exercise}
Let \( a \) and \( b \) be nonzero integers.
\begin{enumerate}[(1)]
\item Prove that the least common multiple of \( a \) and \( b \) exists. 
\item Prove that if \( k \in \mathbb Z \) is a common multiple of \( a \) and \( b \), then \( \mathrm{lcm}(a,b) \) divides \( k \). (Hint: divide \( k \) by \( \mathrm{lcm}(a,b) \) using the division algorithm.)
\end{enumerate}
\end{Exercise}

\begin{Solution}
(1) Both \( ab \) and \( -ab \) are common multiples of \( a \) and \( b \), and as at least one of them is positive, \( a \) and \( b \) have a positive common multiple.
Therefore, the set of positive common multiples of \( a \) and \( b \) is a nonempty subset of the natural numbers.
The well-ordering principle implies that this set has a least element, and hence the least common multiple of \( a \) and \( b \) exist.

(2) Let \( k \in \bz \) be a common multiple of \( a \) and \( b \), and let \( m = \mathrm{lcm}(a,b) \). 
By the division algorithm, there exists \( q, r \in \bz \) such that \( k = mq + r \) and \( 0\leq r < m \). 
Observe that as both \( k \) and \( m \) are common multiples of \( a \) and \( b \), we have that \( k-mq = r \) is a common multiple of \( a \) and \( b \) as well. 
Therefore, as \( m \) is the least positive common multiple of \( a \) and \( b \), \( r \) cannot be positive, i.e., \( r \leq 0 \). 
It follows that \( r = 0 \), as \( r \geq 0 \), and hence \( m \) divides \( k \). 
\end{Solution}


\medskip
\begin{ExChallenge}
Let \( a, b \in \bn \).
\begin{enumerate}[(1)]
\item Prove that the product of \( \mathrm{lcm}(a,b) \) and \( \mathrm{gcd}(a,b) \) is equal to \( ab \). (Hint: the product \( ab \) is divisible by \( d = \mathrm{gcd(a,b)} \). Let \( m = ab/d \). Now, let \( \ell \) be the least common multiple of \( a \) and \( b \). Write \( d \) as a linear combination in \( a \) and \( b \), and use this to express the fraction  \( \ell / m \) as an integer.)
\item Prove that \( \mathrm{lcm}(a,b) = ab \) if and only if \( \mathrm{gcd}(a,b) = 1 \). 
\end{enumerate}
\end{ExChallenge}

\begin{Solution}
(1) Let \( \ell = \lcm(a,b) \), and let \( d = \gcd(a,b) \).
As \( ab \) is divisible by \( d \), there exists \( m \in \bn \) such that \( ab = md \). 
We need to show that \( m = \ell \). 

We first establish that \( \ell \leq m \). 
As \( d \mid b \), there exists \( q \in \bz \) such that \( b = dq \).
By substitution, we have \( ab = aqd = md \), and hence \( m = aq \); in particular, \( a \mid m \).
Similarly, \( b \mid m \).
Therefore, \( m \) is a common multiple of \( a \) and \( b \), and hence \( \ell \leq m \), as claimed. 

Next, we establish that \( m \leq \ell \) by showing that \( m\mid \ell \). 
Let \( s, t \in \bz \) such that \( d = as + bt \). 
It is notationally convenient to work in the rational numbers, and so we will do so despite not discussing the rationals in class yet.
We compute:
\begin{align*}
\frac \ell m 	& = \frac \ell {ab/d} \\
			& = \frac {\ell d}{ab} \\
			& = \frac{ \ell(as + bt)}{ab} \\
			& = s\left(\frac {\ell}{b}\right) + t\left(\frac{\ell}a\right).
\end{align*}
Now, as \( b \mid \ell \) and \( a \mid \ell \), we have that \( s\left(\frac {\ell}{b}\right) + t\left(\frac{\ell}a\right) \) is an integer, and hence \( m \mid \ell \), as claimed. 
We have shown that \( m \leq \ell \) and \( \ell \leq m \), and hence \( m = \ell \) and \( \ell d = ab \), as desired. 

(2) Let \( \ell \) and \( d \) denote the least common multiple and the greatest common divisor, respectively, of \( a \) and \( b \).
We have shown that \( \ell d = ab \).
Therefore, if \( d = 1 \), then \( \ell = ab \).
And, conversely, if \( \ell  = ab = \ell d \), then \( d = 1 \).
\end{Solution}

\end{document}

