\documentclass{article}
\usepackage{amsmath, amssymb,verbatim, amsthm, graphicx}

%exercise environment
\newcounter{exercise}
\setcounter{exercise}{0}
\newenvironment{exercise}{\addtocounter{exercise}{1} \noindent{\bf{Exercise \theexercise.}}}{\vspace{.5cm}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}

\textwidth 6.5in
\textheight 9in
\oddsidemargin 0in
\evensidemargin 0in
\headsep -0.5in

\setlength{\parskip}{0.25cm}

\pagenumbering{gobble}

\begin{document}

\begin{center}
\includegraphics[width=0.5in]{../ltr-logo.jpg}
\end{center}

\noindent{\Large{\textsc{Number Theory \hfill Assignment 7.1  \\ Fall 2023 \hfill Due October 18}}}

\large

\vspace{1cm}

\begin{exercise}
Textbook exercise 2.5.2.
\end{exercise}

\begin{exercise}
Textbook exercise 2.5.5.
\end{exercise}


\begin{exercise}
We can provide an alternate proof of Theorem 2.9 using a little linear algebra as follows.  Let $a,b,c \in \Z$ with $ab \ne 0$.  B\'{e}zout's Lemma implies that $ax+by = c$ has a solution $(x_0 \,\,\, y_0)^T \in \Z^2$ if and only if $(a,b)|c$.  Assume that this is the case.

\begin{itemize}

\item[\bf a.]  The equation $ax+by=c$ can be written in matrix form as 
\[
\underbrace{\left( a \,\,\, b \right)}_{A} \underbrace{\left( \begin{matrix} x \\ y  \end{matrix} \right)}_{\mathbf{x}} = c.
\]
A standard result from linear algebra states that the solutions $\mathbf{x} \in \Q^2$ to $A \mathbf{x} = c$ are given by
\[
\mathbf{x} = \mathbf{x}_0 +  \mathbf{z},
\]
where $\mathbf{x}_0 = (x_0 \,\,\, y_0)^T$ and $\mathbf{z} \in \Q^2$ is any vector in the nullspace of $A$.  Use the Rank Theorem to show that the nullspace of $A$ is 1-dimensional, and is $\Q$-spanned by $(-b \,\,\, a)^T$.  Conclude that the solutions to $A \mathbf{x} = c$ with $\mathbf{x} \in \Q^2$ are given by
\[
\mathbf{x} = \mathbf{x}_0 + t \left( \begin{matrix} -b \\ a \end{matrix} \right), \,\,\, t \in \Q.
\]

\item[\bf b.]  Continuing part {\bf a}, show that $\mathbf{x} \in \Z^2$ if and only if $t(-b \,\,\, a)^T \in \Z^2$ if and only if $at, bt \in \Z$ if and only if $t \in \frac{1}{(a,b)} \Z$. [{\em Suggestion.}  Write $ra + sb = (a,b)$ with $r,s \in \Z$ and multiply both sides by $t$.]

\item[\bf c.]  Conclude that $A \mathbf{x} = c$ with $\mathbf{x} \in \Z^2$ if and only if 
\[
\mathbf{x} = \mathbf{x}_0 + \frac{\ell}{(a,b)} \left( \begin{matrix} -b \\ a \end{matrix} \right), \,\,\, \ell \in \Z.
\]
Show that this is equivalent to the conclusion of Theorem 2.9.
\end{itemize}

\end{exercise}

\vspace{1cm}










\end{document}
 