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

% 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/601 \\
{Due Wednesday, February 14, 2024\footnote{As CUNY is closed on Monday, I will not have office hours.  So, if you would like, you can turn in your assignment by Friday, February 16 by dropping it off in my mailbox in the math office, Kiely 243, or sliding it under my office door, Kiely 507.}} \\[-2mm]
\line(1,0){470}

\medskip

{\bf Instructions.} \textit{Read the appropriate homework guide (\href{http://qc.edu/~nvlamis/301S24/Homework_Guide_301.pdf}{Homework Guide for 301} or \href{http://qc.edu/~nvlamis/301S24/Homework_Guide_601.pdf}{Homework Guide for 601}) to make sure you understand how to successfully complete the assignment. 
All claims must be sufficiently justified. }


\medskip
\begin{Exercise}
Let \( S \) be a finite subset of \( \bn \).
Prove that \( S \) has a maximum, that is, prove that there exists \( s \in S \) such that \( s' \leq s \) for all \( s' \in S \). 
\end{Exercise}

\medskip
\begin{ExGraded}
Let \( a,b \in \bz \smallsetminus\{0\} \), and let \( c \in \bz \). 
Prove that \( c \) is a linear combination of \( a \) and \( b \) if and only if \( \gcd(a,b) \) divides \( c \). 
\end{ExGraded}

\medskip
\begin{Exercise}
Let \( x \in \bz\smallsetminus\{1\} \). 
Use induction to prove that 
\[ \frac{x^n-1}{x-1} = \sum_{i=0}^{n-1} x^i  \]
for all \( n \in \mathbb N \).
(Note: you are inducting on \( n \), not \( x \).)
\end{Exercise}

\medskip
\begin{Exercise} Complete the following exercises from \href{http://abstract.ups.edu/aata/integers-exercises.html}{Section~2.4} in the course textbook:

\# 5, 15, 16, 27, \textbf{*28} (you will need to use Exercise 3), 31
\end{Exercise}

\textbf{Note that 28 above is starrred.}

\medskip
\textbf{Definition.} Given two nonzero integers \( a \) and \( b \), an integer \(c \) is a \emph{common multiple} of \( a \) and \( b \) if \( a \mid c \) and \( b \mid c \). The \emph{least common multiple} of \( a \) and \( b \), denoted \( \mathrm{lcm}(a,b) \), is the smallest positive common multiple of \( a \) and \( b \).


\medskip
\begin{ExGraded}
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{ExGraded}


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


\end{document}

