\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 1}} \hfill MATH 301/601 \\
{Solutions to graded problems \\[-2mm]
\line(1,0){470}
\setcounter{Exercise}5
\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}
\begin{proof}
By the division algorithm, there exists \( k \in \bz \) such that either \( n = 2k \) or \( n = 2k+1 \), that is, either \( n \) is even or odd, respectively.
Also, by the division algorithm, there exists unique \( q, r \in \bz \) such that \( n^2 = 4q + r \) with \( r \in \{0, 1,2, 3\} \).
If \( n = 2k \), then \( n^2 = (2k)^2 = 4k^2 \), and hence, \( q = k^2 \) and \( r = 0 \).
Otherwise, \( n = 2k+1 \) and \( n^2 = (2k+1)^2 = 4(k^2+k)+1 \), and hence, \( q = k^2+k \) and \( r = 1 \).
In either case, \( r \in \{0,1\} \), as desired.
\end{proof}
\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}
\begin{proof}
Let \( S \) be a nonempty subset of \( \bn \times \bn \).
Let \[ T = \{ a \in \bn : \text{there exists } b \in \bn \text{ such that } (a,b) \in S \}. \]
As \( S \) is nonempty, so is \( T \).
Therefore, we can apply the well-ordering principle to \( T \) to obtain its least element, call it \( x \).
Now, let \( U = \{ b \in \bn : (x,b) \in S\} \).
By the construction of \( x \), we know that \( U \) is nonempty, so we can apply the well-ordering principle to \( U \) to obtain its least element, call it \( y \).
By construction, \( s = (x,y) \in S \), and we claim that \( s \) is the least element of \( S \).
Indeed, let \( s' = (x', y') \in S \).
Then, \( x' \in T \), and hence \( x \leq x' \).
If \( x < x' \), then \( s < s' \); otherwise, \( x' = x \), and \( y' \in U \).
Therefore, \( y' \leq y \), and hence \( s = (x,y) \leq (x, y') = s' \).
In either case, we have \( s \leq s' \), as desired.
\end{proof}
\end{document}