\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{\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 1}} \hfill MATH 301/601 \\
{Due Wednesday, February 7, 2024} \\[-2mm]
\line(1,0){470}

\bigskip

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

\bigskip



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

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

\# 22, 24
\end{Exercise}

\bigskip
\begin{ExGraded}
(1) Give an example of a function \( \mathbb N \to \mathbb N \) that is injective but not surjective. 
(2) Give an example of a function \( \mathbb N \to \mathbb N \) that is surjective but not injective.
(3) Give an example of a bijection from \( \mathbb N \to \mathbb Z \). 
\end{ExGraded}

\bigskip
\begin{Exercise}
Let \( a,b,c,m,n \in \mathbb Z \). 
Prove that if \( a \mid b \) and \( a \mid c \), then \( a \mid (mb + nc) \). 
\end{Exercise}

\bigskip
\begin{Exercise}
Let \( a, b \in \mathbb Z \). 
Prove that if \( a \mid b \) and \( b \mid a \), then either \( a = b \) or \( a = -b \).
\end{Exercise}

\bigskip
\begin{ExGraded}
Let \( S \subset \mathbb N \) such that \( 1 \in S \) and \( n+1 \in S \) whenever \( n \in S \). 
Prove that \( S = \mathbb N \). (Hint: Use the well-ordering principle.)
\end{ExGraded}

\bigskip
\begin{ExGraded}
Let \( n \in \mathbb N \).
Prove that the remainder obtained from dividing \( n^2 \) by 4 is either 0 or 1. 
\end{ExGraded}

\bigskip
\begin{ExChallenge}
Define the ordering \( < \) on \( \mathbb N \times \mathbb N \) by \( (a,b) < (c,d) \) if \( a < c \) or \( a=c \) and \( b < d \) (this is called the \emph{lexicographical ordering}).
Prove that \( (\mathbb N \times \mathbb N, <) \) is well ordered, that is, show that given a nonempty subset \( S \) of \( \mathbb N \times \mathbb N \) there exists \( s \in S \) such that \( s < s' \) for all \( s' \in S \smallsetminus \{s\} \).
\end{ExChallenge}

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

%\bigskip
%\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 \).


%\bigskip
%\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}
%
%
%\bigskip
%\begin{ExChallenge}
%Let \( a \) and \( b \) be nonzero integers. 
%\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 \( k \) be a common multiple of \( a \) and \( b \). Write \( d \) as a linear combination in \( a \) and \( b \), and use this to express the fraction  \( k / 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}

