\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim}
\usepackage{microtype}
\usepackage{url}

\addtolength{\evensidemargin}{-.8in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.4in}
\addtolength{\textheight}{1.9in}
\addtolength{\topmargin}{-.7in}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{challenge}[theorem]{Challenge Problem}

\title{\vspace{-50pt}Elementary Number Theory\\
\normalsize Math 175, Section 30, Autumn 2010\\
\large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\
Tom Church ({\tt tchurch@math.uchicago.edu})\\
\url{www.math.uchicago.edu/~tchurch/teaching/175/}}
\author{}
\date{}

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

% \DeclareMathOperator{\sin}{sin}   %% just an example (it's already defined)
\DeclareMathOperator{\norm}{norm}


\renewcommand{\baselinestretch}{1.2}
\begin{document}
\maketitle
\setcounter{section}{1}
\vspace{15pt}
\begin{center}
{\huge \bf Script 1: Divisibility in the Integers}
\end{center}

\vspace{120pt}
\normalsize
\begin{definition}
Let $\Z$ be the \emph{integers}, that is, the unique
ordered commutative ring with identity whose positive elements satisfy the well-ordering property.
In other words, the integers satisfy the following axioms:

\begin{enumerate}
{\bf \item[E1.]  (Reflexivity, Symmetry, and Transitivity of Equality)}

%\begin{center}
\begin{tabular}{ll}
Reflexivity of Equality & If $a\in {\mathbb Z}$, then $a=a$. \\
Symmetry of Equality & If $a,b\in {\mathbb Z}$ and $a=b$, then $b=a$. \\
Transitivity of Equality & If $a,b,c\in {\mathbb Z}$ and $a=b$ and $b=c$, then $a=c$. \\
\end{tabular}
%\end{center}

{\bf \item[E2.]  (Additive Property of Equality)}

If $a,b,c\in {\mathbb Z}$ and $a=b$, then $a+c=b+c$.

{\bf \item[E3.]  (Multiplicative Property of Equality)}

If $a,b,c\in {\mathbb Z}$ and $a=b$, then $a\cdot c=b\cdot c$.\pagebreak

{\bf \item[A1.]  (Closure of Addition)}

If $a, b\in {\mathbb Z}$, then $a+b\in {\mathbb Z}$.  

{\bf \item[A2.]  (Associativity of Addition)}

If $a,b,c\in {\mathbb Z}$, then $(a+b)+c=a+(b+c)$.

{\bf \item[A3.]  (Commutativity of Addition)}

If $a, b\in {\mathbb Z}$, then $a+b=b+a$.  

{\bf \item[A4.]  (Additive Identity)}

There is an element $0\in {\mathbb Z}$ such that $a+0=a$ and $0+a=a$
for every $a\in {\mathbb Z}$. 

{\bf \item[A5.]  (Additive Inverses)}

For each element $a\in {\mathbb Z}$, there is a unique element $-a\in {\mathbb Z}$
such that $a+(-a)=0$ and $(-a)+a=0$.  

{\bf \item[M1.]  (Closure of Multiplication)}

If $a, b\in {\mathbb Z}$, then $a\cdot b\in {\mathbb Z}$.  

{\bf \item[M2.]  (Associativity of Multiplication)}

If $a,b,c\in {\mathbb Z}$, then $(a\cdot b)\cdot c=a\cdot (b\cdot c)$.

{\bf \item[M3.]  (Commutativity of Multiplication)}

If $a,b\in {\mathbb Z}$, then $a\cdot b=b\cdot a$.

{\bf \item[M4.]  (Multiplicative Identity)}

There is an element $1\in {\mathbb Z}$ (with $1\neq 0$) such that $a\cdot 1=a$ and
$1\cdot a=a$ for every $a\in {\mathbb Z}$. 

%{\bf \item[M5.]  (Multiplicative Inverses)}

%For each element $a\in {\mathbb R}$ with $a\neq 0$, there is an element $a^{-1}\in {\mathbb R}$
%such that $a\cdot a^{-1}=1$ and $a^{-1}\cdot a=1$.

{\bf \item[D.]  (Distributivity of Multiplication over Addition)}

If $a,b,c\in {\mathbb Z}$, then $a\cdot (b+c)=a\cdot b+a\cdot c$ and $(a+b)\cdot c=a\cdot c+
b\cdot c$.

{\bf \item[O1.]  (Transitivity of Inequality)}

If $a,b,c\in {\mathbb Z}$ and $a<b$ and $b<c$, then $a<c$.

{\bf \item[O2.]  (Trichotomy)}

If $a,b \in {\mathbb Z}$, then exactly one of the following is true:  $a<b$, $a=b$, or $a>b$.

{\bf \item[O3.]  (Additive Property of Inequality)}

If $a,b,c\in {\mathbb Z}$ and $a<b$, then $a+c<b+c$.

{\bf \item[O4.]  (Multiplicative Property of Inequality)}

If $a,b,c\in {\mathbb Z}$ and $a<b$ and $c>0$, then $a\cdot c<b\cdot c$.

{\bf \item[W.]  (Well-Ordering Property)}

If $S$ is a non-empty set of positive integers, then $S$ has a least element (that is, there
is some $x\in S$ such that if $y\in S$, then $x\leq y$).
\end{enumerate}
\end{definition}\pagebreak
%
%\begin{definition}
%(Subtraction)  We define the difference $a-b$ to be the sum $a+(-b)$.
%\end{definition}

\renewcommand{\baselinestretch}{1.6}

\begin{center}\large \bf To prepare for class on Thursday, September 30: Theorem~\ref{addcancel} through \ref{multcancel}.\end{center}

For Theorems~\ref{addcancel} through \ref{multneg}, you may use Axioms E1--E3, A1--A5, M1--M4, and D.
\begin{theorem}[Cancellation Law for Addition]
\label{addcancel}
If $a+c=b+c$, then $a=b$.
\end{theorem}

\begin{theorem}
If $a\in\Z$, then $-(-a)=a$.
\end{theorem}

\begin{theorem}
If $a\in \Z$, then $(-1)\cdot a=-a$.
\end{theorem}

\begin{theorem}
If $a\in \Z$, then $a\cdot 0 =0$.
\end{theorem}

\begin{theorem}
\label{multneg}
If $a, b\in \Z$, then:
\begin{enumerate}
\item[(i)]  $a(-b)=-ab$ and $(-a)b=-ab$

\item[(ii)]  $(-a)(-b)=ab$
\end{enumerate}
\end{theorem}

\begin{challenge}Prove Theorem~\ref{addcancel} without assuming that additive inverses are unique (i.e. delete the word "unique" from Axiom A5). Then use Theorem~\ref{addcancel} to prove that $-a$ is in fact unique anyway.\end{challenge}

\medskip For Theorems~\ref{negpos} through \ref{multineq}, you may also use Axioms O1--O4.
\begin{theorem}
\label{negpos}
If $a>0$, then $-a<0$.  (And if $a<0$, then $-a>0$.)
\end{theorem}

\begin{theorem}
If $a<b$ and $c<0$, then $ac>bc$.
\end{theorem}

\begin{theorem}
If $a\neq 0$, then $a^2>0$.
\end{theorem}

\begin{exercise}
Prove that $1>0$.
\end{exercise}

\begin{theorem}
\label{multineq}
If $a\geq 1$ and $b>0$, then $ab\geq b$.
\end{theorem}

\medskip For Theorem~\ref{noint}, you may also use Axiom W.
\begin{theorem}
\label{noint}
There is no integer between 0 and 1.
\end{theorem}

\begin{challenge}
Prove that Axiom W is necessary to prove Theorem~\ref{noint}.
\end{challenge}

\begin{theorem}[Cancellation for Multiplication]
\label{multcancel}
If $a\neq 0$ and $a\cdot b=a\cdot c$, then $b=c$.
\end{theorem}\pagebreak

\begin{definition}  
Let $a, b\in\Z$.  We say that {\em b divides a} (and that $b$ is a {\em divisor} of $a$) and write $b|a$ 
provided that there is some $n\in\Z$ such that $a=b\cdot n$.
\end{definition}

\begin{definition}[Division]
If $b|a$ (with $b\neq 0$) and $c$ is the integer such that $a=b\cdot c$, then we define $\frac{a}{b}=c$.
\end{definition}

\begin{exercise}
Show that $\frac{a}{b}$ is well-defined.
\end{exercise}

\begin{theorem}
If $a|b$ and $a|c$, then $a|(b+c)$ and $a|(b-c)$.
\end{theorem}

\begin{theorem}
If $a|b$ and $c\in\Z$, then $a|(b\cdot c)$.
\end{theorem}

\begin{theorem}
If $a|b$ and $b|c$, then $a|c$.
\end{theorem}

\begin{exercise}
Prove that if $a|b$ and $a|c$ and $s,t\in\Z$, then $a|(sb+tc)$.
\end{exercise}

%\begin{definition}
%If $a\in\Z$, we define the {\em absolute value} of $a$ by the 
%following notation and with the following meaning:
%$$
%|a|=\left\{
%\begin{array}{rcl}
%a & , & \mbox{if $a\geq 0$} \\
%-a & , & \mbox{if $a<0$} \\
%\end{array}
%\right.
%$$
%\end{definition}
\bigskip
\begin{theorem}
If $a>0$, $b>0$ and $a|b$, then $a\leq b$.
\end{theorem}

\begin{exercise}
Show that any non-zero integer has a finite number of divisors.
\end{exercise}

\begin{theorem}
If $a|b$ and $b|a$, then $a=\pm b$.
\end{theorem}

\begin{theorem}
If $m\neq 0$, then $a|b$ if and only if $ma|mb$.
\end{theorem}

\begin{theorem}
(The Division Algorithm)  If $a, b\in\Z$ and $b>0$, then there exist unique integers $q$ and $r$
such that $a=bq+r$ and $0\leq r< b$.
\end{theorem}

\bigskip
\begin{definition}
Let $a,b\in\Z$, not both zero.  
A {\em common divisor} of $a$ and $b$ is defined to be any integer $c$ such that $c|a$ and $c|b$.
The {\em greatest common divisor} of $a$ and $b$ is denoted $(a, b)$ and 
represents the largest element of the set $\{c\in\Z\mid c|a, c|b\}$. 
\end{definition}

\begin{exercise}
Show that $(a, b)=(b, a)=(a, -b)$.
\end{exercise}

\begin{theorem}
If $d|a$ and $d|b$, then $d|(a,b)$.  (Hint:  Do Theorem~\ref{next} first.)
\end{theorem}

\begin{theorem}
\label{next}
If $d=(a,b)$, then there exist integers $x, y$ such that $d=xa+yb$.
\end{theorem}

\begin{theorem}
If $m\in\Z$ and $m>0$, then $(ma, mb)=m(a,b)$.
\end{theorem}

\begin{theorem}
If $d|a$ and $d|b$ and $d>0$, then $(\frac{a}{d}, \frac{b}{d})=\frac{(a,b)}{d}$.
\end{theorem}

\begin{definition}
Two integers $a$ and $b$ are said to be {\em relatively prime} if $(a, b)=1$.
\end{definition}

\begin{theorem}
If $(a, m)=1$ and $(b, m)=1$, then $(ab, m)=1$.
\end{theorem}

\begin{theorem}
If $c|ab$ and $(c, b)=1$, then $c|a$.
\end{theorem}

\begin{theorem}
(The Euclidean Algorithm)

Let $a, b\in\Z$ be positive integers. If we apply the Division Algorithm sequentially as follows:

\[
\begin{array}{rclll}
a &=& bq_1+r_1 & \phantom{MMM} & 0< r_1<b \\
b &=& r_1q_2+r_2 & & 0<r_2<r_1 \\
r_1 &=& r_2q_3+r_3 & & 0<r_3<r_2 \\
& \vdots & & & \\
r_{k-2} &=& r_{k-1}q_k+r_k & & 0<r_k<r_{k-1} \\
r_{k-1} &=& r_kq_{k+1} \\
\end{array}\]
then $r_k=(a,b)$.
\end{theorem}

\bigskip {\large Some definitions that will come in handy:}

\begin{definition}[Subtraction] We define the \emph{difference} $a-b$ to be the sum $a+(-b)$.
\end{definition}

\begin{definition}[Absolute value]
If $a\in\Z$, we define the {\em absolute value} of $a$ by the 
following notation and with the following meaning:
\[|a|=\left\{
\begin{array}{rl}
a &  \mbox{if $a\geq 0$} \\
-a  & \mbox{if $a<0$} \\
\end{array}
\right.\]
\end{definition}

%\vspace{30pt}
%\hspace{2.5in}
%\copyright  {\tt 2010 Tom Church (based on script by John Boller)}

\end{document}