\documentclass[11pt,oneside,reqno]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath, multicol, enumerate}
\usepackage{pdfsync}%leaves makers for tex searching

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}


%%% Environments %%%--------------------------------------------------------- 
\newenvironment{ans}{\medskip \paragraph*{\emph{Answer}.}}{\hfill \break \rule{1.5cm}{0.4pt} \medskip }
\newenvironment{sketch}{\medskip \paragraph*{\emph{Proof sketch}.}}{ \medskip }
\newenvironment{summary}{\medskip \paragraph*{\emph{Summary}.}}{  \hfill \break  \rule{1.5cm}{0.4pt} \medskip }
\newcommand\Ans[1]{\hfill \emph{Answer:} {#1}}

%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}
	\newtheorem{lem}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}


%%% Pictures %%%--------------------------------------------------------- 
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[pdftex,bookmarks]{hyperref}
\usetikzlibrary{scopes}
\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=2pt]
\tikzstyle{bV}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]
\tikzstyle{over}=[draw=white,double=black,line width=3pt]

\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}



%%% Color  %%%--------------------------------------------------------------
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}

%%% Alphabets %%%--------------------------------------------------------
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\ii{\mathbf{i}}\def\jj{\mathbf{j}}\def\kk{\mathbf{k}}\def\uu{\mathbf{u}}\def\vv{\mathbf{v}}\def\ww{\mathbf{w}}

\def\<{\langle} \def\>{\rangle}
\def\half{\hbox{$\frac12$}}
\def\id{\mathrm{id}}
\def\img{\mathrm{img}}
\def\vep{\varepsilon}
\def\lcm{\mathrm{lcm}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\HW{9}
\def\DUE{11/20/2018}
\def\NAME{YOUR NAME HERE}
\title[Homework \HW]{Homework \HW\\
Math 308\\
\small Due: \DUE}
\author{}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
%\maketitle %Comment out this line, and uncomment the following for your assignment
\begin{flushright}
\NAME\\
Math 308\\
Homework \HW\\
\DUE
\end{flushright}


\noindent Throughout, let $a, b$, and $c$ be non-zero integers. 

\begin{enumerate}[1.]
\item Consider the following statements:
\begin{enumerate}[\bf i.]
\item $a$ is divisible by 3;
\item  $a$ is divisible by 9;
\item $a$ is divisible by 12;
\item  $a = 24$;
\item  $a^2$ is divisible by 3;
\item  $a$ is even and divisible by 3.
\end{enumerate}
Which conditions are necessary for $a$ to be divisible by 6? Which are sufficient? Which are necessary and sufficient?


\item Run the Euclidean algorithm with $a = 30$, $b=12$.


\item Recall from lecture that executing the Euclidean algorithm for $a = 100$ and $b=36$ gives the following equations:
\begin{align}
100 & = 36 * 2 + 28, \tag{E1}\\
36 &= 28 * 1 + 8, \tag{E2}\\
28 & = 8*3 + 4, \tag{E3}\\
8 & = 4*2 + 0. \tag{E4}
\end{align}
\begin{enumerate}[(a)]
\item Follow these steps to express 4 as an \emph{integer combination} of 100 and 36, i.e., find (possibly negative) integers  $x$ and $y$ such that $100x + 36 y = 4$:
\begin{enumerate}[(i)]
\item Use equation (E3) to express 4 as an integer combination of 8 and 28 (find integers $x$ and $y$ 
such that $8x + 28 y = 4$).
\item Use equation (E2) to express 8 as an integer combination of 28 and 36 . 
\item Use equation (E1) to express 28 as an integer combination of 36 and 100. 
\item Plug your equation from part (ii) into your equation in part (i), expanding and simplifying, to express 4 as an integer combination of 28 and 36.
\item Plug your equation from part (iii) into your equation in part (iv), expanding and simplifying, to express 4 as an integer combination of 36 and 100.
\end{enumerate}
\item Make an argument (write an informal proof) justifying the following claim:\\
\emph{For any positive integers $a$ and $b$, there exist integers $x$ and $y$ satisfying
$\gcd(a,b) = ax + by.$}
\end{enumerate}

\item Consider Euclid's Lemma and its proof from Chapter 28 of ``How to think\dots'': 

\begin{quote}
\textbf{Euclid's Lemma.} Suppose that $n$, $a$, and $b$ are natural numbers. If $n|ab$ and $\gcd(n, a) = 1$, then $n|b$.
\begin{proof}
Since $\gcd(n, a) = 1$, there exist integers $k$ and $\ell$ such that $kn + \ell a = 1$. Thus $knb + \ell ab = b$. We obviously have $n|knb$. We also have $n|ab$, so $n|lab$. Thus $n|knb + lab$, i.e.\ $n|b$.\end{proof}
\end{quote}

\begin{enumerate}[(a)]
\item Analyze the theorem statement: give examples, non-examples, assumptions and conclusions, compare to other results, etc. Compare to the statement given in class. 
\item Identify in the proof (here) where the hypotheses were used. 
\item What theorems/lemmas/etc.\ were used in the proof?
\item Compare/contrast this proof to the proof from class. 
\item Analyze what happens when we drop the hypothesis that $\gcd(n,a) = 1$.
\end{enumerate}

\item Prove the following. 
\begin{enumerate}[(a)]
\item We have $a|b$ if and only if $-a|b$.
\item If $\delta$ is a common divisor of $a$ and $b$, then $\delta | \gcd(a,b)$.
\item If  $a \ge 4$ is not prime, then $a | (a-1)!$. 
\end{enumerate}

\item Use strong induction to prove the division algorithm: 
\begin{quote}For any $a, b \in \ZZ$ with $b \neq 0$, there are unique integers $q$ and $r$ satisfying 
$$a = bq + r \qquad \text{ and } \qquad 0 \leq r < |b|.$$
\end{quote}
{[Recall: We sketched a proof in class. You'll need to do two cases.]}
\item An integer $\ell$ is called a \emph{common multiple} of non-zero integers $a$  and $b$ if $a|\ell$ and $b|\ell$. The smallest positive such $\ell$ is called the \emph{least common multiple} of $a$ and $b$, denoted $\lcm(a,b)$. For example, $\lcm(3, 7) = 21$ and $\lcm(12, 66) = 132$.
\begin{enumerate}[(a)]
\item Compute $\lcm(12, 8)$,  $\lcm(30, 20)$, $\lcm (-10, 22)$, and $\lcm(9, 10)$.
\item Prove that if $a | m$ and $b | m$, then $\lcm(a,b) | m$.
\item Prove that for any $r \ZZ$, we have  $\lcm(ra, rb) = r\ \lcm(a, b)$.
\item Show that  $ab = \gcd(a,b) \lcm(a,b)$.
\end{enumerate}




\end{enumerate}



\end{document}