\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 3}} \hfill MATH 301/601 \\
{Due Thursday, February 22, 2024} \\[-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}
Complete Exercise \#1 from \href{http://abstract.ups.edu/aata/groups-exercises.html}{Section~3.5} in the course textbook
\end{Exercise}

\bigskip
\begin{Def}
An \emph{equivalence relation} on a set \( S \) is a binary relation \( \sim \) that is:
\begin{enumerate}[(i)]
\item \emph{reflexive}, that is, \( a \sim a \) for all \( a \in S \);
\item \emph{symmetric}, that is, \( a \sim b \) implies \( b \sim a \) for all \( a, b \in S \); and
\item \emph{transitive}, that is, \( a \sim b \) and \( b \sim c \) implies \( a \sim c \) for all \( a, b, c \in S \).
\end{enumerate}
\end{Def}

\medskip
\begin{Exercise}
Let \( n \in \bn \).
Prove that equivalence modulo \( n \) is an equivalence relation on \( \mathbb Z \).
\end{Exercise}

\medskip
\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 \).
(Hint: Use the division algorithm.)
\end{ExGraded}

\medskip
\begin{Exercise}
Let \( n \in \bn \), and let \( a, b \in \bz \).
Prove that if \( a \equiv b \pmod n \), then \[ \gcd(a,n) = \gcd(b,n) .\]
\end{Exercise}


\medskip
\begin{ExGraded}
Let \( n \in \mathbb N \) with \( n > 1 \), and let \( a \in \mathbb Z \).
\begin{enumerate}[(a)]
\item
Prove that if \( \gcd(a,n) = 1 \) and \( b,c \in \bz \) such that \( ab \equiv ac \pmod n \), then \( b \equiv c \pmod n \). 
\item
Give an example of integers \( n, a, b, c \) such that \( a \not\equiv 0 \pmod n \), \( b \not\equiv c \pmod n \), and \( ab\equiv ac \pmod n \).
\end{enumerate}
\end{ExGraded}

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

\bigskip\bigskip
\begin{center}
(Turn page over.)
\end{center}
\newpage



\medskip
\begin{Exercise}
Let \( n \in \mathbb N \).
\begin{enumerate}[(a)]
\item
Prove that \( 10^n \equiv 1 \pmod 9 \). (There are numerous ways to see this.  One way is to use induction.)
\item (Divisibility by 9)
Define \( h\co \mathbb N \to \mathbb Z \) by \[ h(n) = \sum_{j=0}^{k}  a_j, \]
where \[ n = \sum_{j=0}^{k} (a_j \cdot 10^j). \]
In words, \( h(n) \) is the  sum of the digits of \( n \) when written in base 10.
For example, if \( n = 27301 \), then \( h(n) = 1+0+3+7+2 = 13 \). 
Prove the following statement: 
Let \( n \in \mathbb N \).
Then,  \( 9 \mid n \) if and only if \( 9 \mid h(n) \). 
(Hint: You will have to use part (a).)
\end{enumerate}
\end{Exercise}



\medskip
\begin{ExGraded}
Let \( n \in \mathbb N \).
\begin{enumerate}[(a)]
\item
Prove that \( 10^n \equiv (-1)^n \pmod {11} \).
(Hint: use induction.)
\item (Divisibility by 11)
Define \( f\co \mathbb N \to \mathbb Z \) by \[ f(n) = \sum_{j=0}^{k} (-1)^j a_j, \]
where \[ n = \sum_{j=0}^{k} (a_j \cdot 10^j). \]
In words, \( f(n) \) is the alternating sum of the digits of \( n \) when written in base 10.
For example, if \( n = 27301 \), then \( f(n) = 1-0+3-7+2 = -1 \). 
Prove the following statement: Let \( n \in \mathbb N \).
Then,  \( 11 \mid n \) if and only if \( 11 \mid f(n) \). 
(Hint: You will have to use part (a).)
\end{enumerate}
\end{ExGraded}



\end{document}

