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


\bigskip
\begin{ExGraded}
Let \( n \in \bn \). 
Prove that given any \( m \in \bz \) there exists a unique element \( a \in \{0, 1, 2, \ldots, n-1 \} \) such that \( m \equiv a \pmod n \).
\end{ExGraded}

\begin{Solution}
Let \( m \in \bz \). 
By the division algorithm, there exists unique \( q, a \in \bz \) such that \( m = qn + a \) and \( a \in \{0, 1, \ldots, n-1\} \). 
Rearranging the above equality, we have that \( m-a = qn \), and hence \( n \mid m-a \).
This implies that \( m \equiv a \pmod n \) and \( a \in \{0, 1, \ldots, n-1\} \), as desired.
It is left to show that \( a \) is unique: let \( a' \in \{0, 1, \ldots, n-1\} \) such that \( m \equiv a' \pmod n \). 
Similar to the above (but in reverse), there exists \( q' \in \bz \) such that \( m = q'n + a' \).
As \( 0 \leq a' < n \), the uniqueness component of the division algorithm implies that \( a' = a \). 
Therefore, there exists a unique \( a \in \{0, \ldots, n-1\} \) such that \( m \equiv a \pmod n \). 
\end{Solution}

\setcounter{Exercise}5

\medskip
\begin{ExChallenge}
Let \( m,n \in \bn \) be relatively prime, and let \( a, b \in \bz \).
Prove that there exists \( x \in \bz \) such that 
\begin{align*}
x &\equiv a \pmod m \\
x &\equiv b \pmod n .
\end{align*}
(Hint: Start by writing 1 as a linear combination of \( m \) and \( n \).) 
\end{ExChallenge}

\begin{Solution}
As \( m \) and \( n \) are relatively prime, there exists \( s, t \in \bz \) such that \( 1 = ms + nt \). 
From this, we see that \( 1- ms = nt \) and \( 1 - nt = ms \), and hence, \( ms \equiv 1 \pmod n \) and \( nt \equiv 1 \pmod m \). 
Setting \( x = bms + ant \), we have \[ x \equiv 0 + ant \equiv a(1) \equiv a \pmod m \] and \[ x \equiv bms + 0 \equiv b(1) \equiv b \pmod n. \] 
Therefore, \( x \) is as desired. 
\end{Solution}

\end{document}

