% If you want to see what things look like for a handout, remove the
% comment from the next line.
\newif\ifHandout%\Handouttrue
\documentclass{book}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Adjust margins and page layout.
\addtolength{\topmargin}{-.5in}
\addtolength{\headsep}{.5in}
\oddsidemargin=.5in
\evensidemargin=.5in
\textwidth=5.5in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Load a bunch of packages that extend the basic capabilities of LaTeX
\usepackage{
amsmath,% AMS basic math stuff
amsthm,% AMS theorem defining stuff
amsfonts,% defines the blackboard bold fonts for \Z, \R, etc
longtable,% used to create the tcproof environment below
verbatim,% allows for verbatim output, and also covering up stuff in comments
xspace,% adds an extra space an the end of some commands
multicol,% allows multicolumn output
tikz,% creates the tikzpicture drawing environment
charter,% changes the default font to charter
framed,% used to color in the TIscreen environment below
}
% the next package defines dingbat fonts. I use dingbat 212 to make a
% thick arrow somewhat like the "to" arrow that's displayed in TI-83
% programming.
\usepackage{pifont}
% Makes section headings and cross references act like links
\usepackage[colorlinks,unicode]{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Create simple shortcut commands. Almost everyone who uses LaTeX
% creates commands like thes.
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
% For some reason basic TeX/LaTeX doesn't define a an lcm command! So
% I create one
\DeclareMathOperator{\lcm}{lcm}
% \cl stands for "class"
\newcommand{\cl}[1]{[#1]}
% \st stands for "such that", used in set builder notation like so
% \{x \st x^2 = 4\}
\newcommand{\st}{\mid}
% Make an equals sign with a question mark over it
\newcommand{\eq}{\stackrel{?}{=}}
% The next line difines a divides sign with a question mark
\newcommand{\divq}{\stackrel{?}{|}}
\newcommand{\forwards}{\mbox{``$\Longrightarrow$''}\xspace}
\newcommand{\backwards}{\mbox{``$\Longleftarrow$''}\xspace}
% this is to highlight words that are being defined and enter.
\newcommand{\define}[1]{\textbf{#1}}
% The names of congruence classes modulo three as I've named them
% (threeven, throd, throve) and as Caytie named them. This way I can
% change the notes/examples whenever I teach this subject to use the
% names students come up with.
\newcommand{\threeven}{pretty\xspace}
\newcommand{\throd}{normal\xspace}
\newcommand{\throve}{ugly\xspace}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Create some slightly more sophisticated custom commands. New
% symbols, or tweaking old ones.
% The next two lines define a reasonable looking not divides sign.
\DeclareMathSymbol{\nmid}{\mathrel}{AMSb}{"2D}
\newcommand{\notdiv}{\nmid}
% Make the tilde command wider
\renewcommand{\tilde}{\widetilde}
% the following two commands change the way the footnote symbol is
% made to be old fashioned: *, dagger, etc.
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
% This is how I create marks in the text showing where we finished on
% a given day.
\def\endclass#1{\par\noindent\hrulefill\fbox{\tiny This is where we
ended on #1}\hrulefill\vskip 5pt plus 1pt\par }
% Now I redefine things to produce the headings I want.
\pagestyle{headings}
\makeatletter
% First I redefine the \today command
\edef\today{%
\the\year/\two@digits{\the\month}/\two@digits{\the\day}}
% Now I put the date in the heading
\renewcommand{\@evenhead}{\emph{Introduction to Abstract Algebra}
(v. \today)
\hfill W. Ethan Duckworth \hfill \thepage}
\renewcommand{\@oddhead}{(version \today) \hfill \thepage}
\makeatother
% Redefine the emptyset symbol so it looks nicer
\DeclareMathSymbol{\varnothing}{\mathord}{AMSb}{"3F}
\renewcommand{\emptyset}{\varnothing}
% If I'm making handouts I (1) sometimes insert a pagebreak so the
% Example starts at the top of the page, and (2) cover up the
% solutions (turn them white!)
\ifHandout
\newcommand{\handoutpagebreak}{\newpage}
\newenvironment{solution}
{\smallskip\par\noindent\emph{Solution: }\color{white}}
{}
\else
\newcommand{\handoutpagebreak}{}
\newenvironment{solution}
{\smallskip\par\noindent\emph{Solution: }}
{}
\fi
% The next few commands are for simulating the output of a TI screen.
\colorlet{shadecolor}{gray!35}
\newenvironment{TIscreen}
{\begin{center}\tt
\renewcommand{\in}[1]{##1\\}
\newcommand{\out}[1]{\mbox{}\hfill##1\\}
\begin{minipage}{2in}\begin{snugshade}}
{\end{snugshade}\end{minipage}\end{center}}
% The next environment is for creating two column proofs.
\newenvironment{tcproof}[1]
{\smallskip\par\begin{longtable}{@{}p{.45\textwidth}p{.45\textwidth}@{}}
\multicolumn{2}{@{}l}{\emph{#1}}\\[\smallskipamount]
Assertion & Justification \endfirsthead
Assertion & Justification \endhead
\hline }
{\end{longtable}\qed\smallskip\par}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The next page or two of stuff is devoted to creating and
% manipulating the environments for lemma, proof, example, etc.
% The first part is pretty simple, and almost everyone has commands
% like this in every paper, article, book, etc.
%
% We start with things like lemmas, theorems, etc.
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{cor}[lemma]{Corollary}
\newtheorem*{scholium}{Scholium}
% Now we create things like definitions, examples, comments, etc.
\theoremstyle{definition}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{example}[lemma]{Example}
\newenvironment{comments}{}{}
% Now I add a horizontal line at the end of definitions, examples,
% etc. Note: in theory the ntheorem package should make this easy,
% but the last time I tried it (2010) the package didn't always work.
\newcommand{\myrule}{\nobreak\par\noindent\mbox{}\hspace*{.333333\textwidth}%
\rule{.333333\textwidth}{.01in}\hspace*{.33333\textwidth}\par}
\makeatletter
\g@addto@macro\enddefinition\myrule
\g@addto@macro\endexample\myrule
\g@addto@macro\endcomments\myrule
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The stuff that follows is a bit tricky, and is well more than most
% people do with LaTeX. The basic idea is that I want to be able to
% show only examples, or only definitions, or hide only proofs, etc.
\makeatletter
% the following key values give the set up for hiding certain
% environemnts. Note that "true" is just a dummy value. It would work
% equally well with "foo". Each one of these redefines the outer
% environment for an atom to turn the whole thing into a hidden
% comment. Note that the environments theorem, example, etc. do not
% have to be written in any special way for hide and show to work.
% They get clobbered by hide.
\define@key{hide}{scholium}[true]{\renewenvironment{scholium}{\comment}{\endcomment}}
\define@key{hide}{proof}[true]{\renewenvironment{proof}{\comment}{\endcomment}}
\define@key{hide}{lemma}[true]{\renewenvironment{lemma}{\comment}{\endcomment}}
\define@key{hide}{comments}[true]{\renewenvironment{comments}{\comment}{\endcomment}}
\define@key{hide}{cor}[true]{\renewenvironment{cor}{\comment}{\endcomment}}
\define@key{hide}{definition}[true]{\renewenvironment{definition}{\comment}{\endcomment}}
\define@key{hide}{example}[true]{\renewenvironment{example}{\comment}{\endcomment}}
\define@key{hide}{theorem}[true]{\renewenvironment{theorem}{\comment}{\endcomment}}
% Now this command can be given a comma separated list of names to
% hide. Thus, \HideEnvirons{ example, proof} would hide all examples
% and proofs.
\newcommand{\HideEnvirons}[1]{\setkeys{hide}{#1}}
% The \ShowEnvirons command works like this: if it's argument is foo,
% it redefines the *hide* family key for foo to do nothing. Then, it
% issues a \HideEnvirons command containing a list of all the atom
% types. So, everything is hidden *unless* the hide-family key has
% been redefinied.
\define@key{show}{scholium}[true]{\define@key{hide}{scholium}{}}
\define@key{show}{proof}[true]{\define@key{hide}{proof}{}}
\define@key{show}{lemma}[true]{\define@key{hide}{lemma}{}}
\define@key{show}{comments}[true]{\define@key{hide}{comments}{}}
\define@key{show}{cor}[true]{\define@key{hide}{cor}{}}
\define@key{show}{definition}[true]{\define@key{hide}{definition}{}}
\define@key{show}{example}[true]{\define@key{hide}{example}{}}
\define@key{show}{theorem}[true]{\define@key{hide}{theorem}{}}
% This command can be given a comma separated list of names to show,
% and only these will be shown. Thus,
% \ShowEnvirons{example,definition} will show only examples and definitions.
\newcommand{\ShowEnvirons}[1]
{\setkeys{show}{#1}\HideEnvirons{%
comments,
cor,
definition,
example,
proof,
theorem,
lemma,
scholium
}}
\makeatother
% Comment out the next line to see the full text
\ShowEnvirons{definition,theorem}
\begin{document}
\tableofcontents
\newpage
\section*{Preface}
\begin{comments}
This text started as a set of lecture notes based on courses I taught
at Loyola College in Maryland from the years 2004 to 2008. The
students who take this course at Loyola have a wide range of
mathematical readiness. Some are eager to start working with abstract
mathematics and proofs, and some are still learning to write proofs,
some prefer computation to theory. These notes are distinguished from
similar texts by the inclusion of more discussion of abstraction and
proofs, include more computations, and more applications.
The text presents a ``rings first'' approach, but starts with the
integers and modular numbers before doing rings from an abstract
approach. An application of some kind is given every few sections.
Examples include: solving a linear Diophantine equation in two
variables, solving a linear modular equation, check-digit schemes, RSA
encryption and AES encryption.
A quick instructor might be able to cover all the topics in this text,
but I prefer to cover a little less and have a better time doing it.
One ``less is more'' approach is to try to get to RSA and AES as
quickly as possible.
One goal is to get to AES. Here's how to find the geodesic path to
AES, by going backwards. AES depends on finite fields, which in turn
depend on polynomials over a field, which depend on polynomials, and
the division algorithm. (Technically, it doesn't require the division
algorithm, but this is the constructive approach, and gives unique
results in the calculations. Also, I prefer to assume results about
which polynomials are irreducible.) Constructing quotient rings of
the polynomial ring should be patterned after the similar construction
of the modular integers from the integers.
Along this path, I prefer to add a few applications to keep the
student's interest. Also, I include material that will help them
understand difficult points on the geodesic path. For instance,
I slow down on modular arithmetic and do it twice. I do RSA as a
warm up to AES. I discuss the role of axiomitization and rigorous
proofs. Finally, I add a small amount of material about rings (basic
definitions, homomorphisms and ideals), since this material is assumed
(by other teachers, other schools, etc.) to be covered in such a
course.
For readers who are interested in further information about these
topics, see
\emph{Men of Mathematics} by E.T. Bell. This book is famous for
having entertaining and short biographies of a large number of
prominent mathematicians (up to 1900).
\emph{Unknown Quantity} by John Derbyshire. This is a history of
algebra, written for a popular audience (and based on secondary
sources).
\emph{Integers, polynomials, rings} by Irving Reiner. This is a
textbook similar in aim and scope to the present set of lecture
notes.
\emph{History of Mathematics} by John Stillwell. This is not a
history book per se, but rather a math book that works its way through
the history of mathematics. In other words, it concentrates more
on the mathematics than on the history. Written as a linear
combination of a math and history text, it's about $\frac 13$ history
and $\frac 23$ math text.
\end{comments}
\chapter{The integers}
\label{chapter_integers}
\section{What are the integers?}
\begin{comments}
What are the integers? How should we even try to answer this
question? Let's cop-out and start with the dictionary. The American
Heritage Dictionary % third edition
says an integer is
\begin{quote}
A member of the set of positive whole numbers ($1$, $2$, $3$,
\dots), negative whole numbers ($-1$, $-2$, $-3$, \dots), and zero
(0).
\end{quote}
Of course a dictionary definition is not meant to be complete in a
technical sense, rather, it is meant to indicate how the word is used,
assuming that the meaning behind the word is already understood. In
any case, ignoring whatever information is given in the phrase ``whole
numbers'' (which American Heritage defines poorly), one might be led
to the following statement: ``An integer is a member of the set
\ldots, $-3$, $-2$, $-1$, $0$, $1$, $2$, $3$, \dots ''.
Again, this statement is useful if one already knows the set being
described, and just needs to connect this to the word ``integer''.
But, this definition is the sort that one might give to a small
child. It is similar to defining ``cat'' by saying ``A cat is the
animal pictured to the right'' (and including a picture).
In contrast, American Heritage gives a \emph{grown up} definition of
cat
\begin{quote}
A small carnivorous mammal (\emph{Felis catus} or \emph{F. domesticus})
domesticated since early times as a catcher of rats and mice and as a
pet and existing in several distinctive breeds and varieties.
% American Heritage
\end{quote}
By the way, this definition is \emph{not} accompanied by a picture!
It is interesting that the dictionary gives a sophisticated, grown up
definition of cat, but an immature definition of integer.
I would like to give a definition of integers, that is modelled very
closely on the dictionary definition of cat. It starts by defining
the thing in question, cat, as a single instance of a wider category
of things, small carnivorous mammal. It then describes a property,
domesticated. Then what a cat does, catches rats and mice. Finally,
something about the appearance.
We'll follow a similar pattern for the integers, in a slightly
different order. In order to describe the integers as an example of
something from a wider category, we must define the category. It is
the category of rings, and we will define what a ring is. We will
define what the integers, and other rings, do: they have operations
that given them a certain life, that make them more about process than
about static existence. Mathematically, this means that rings are
more than just sets, they are sets with additional structure.
Finally, we will describe the properties that integers have, both in
common with other rings, and uniquely to themselves.
\end{comments}
\begin{definition}
\label{definition:informal_integers}
The \define{integers} are a set $\Z$ of elements
$$
\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4,\dots
$$
that have the usual operations\footnote{If we wanted to define the
integers more formally, we would use a more precise statement of
what ``$+$'' and ``$\times$'' are.} of $+$ and $\times$, the usual
relation\footnote{If we were being more formal, we'd list the hidden
assumptions that we're making about ``$<$'': that it is total,
meaning given any two integers we can say that one is smaller than
the other, and that it is transitive, meaning that if $a<b$ and
$b<c$ then $a<c$.} $<$, and that satisfy the following properties,
for all $a,b,c\in \Z$:
\begin{enumerate}
\renewcommand{\theenumi}{\textbf{Z\arabic{enumi}}}
\item
\label{Z_axiom_assoc_addit}
$a+ (b+ c) = (a+ b) + c$,
\item
\label{Z_axiom_commut_addit}
$a+ b = b + a$,
\item
\label{Z_axiom_addit_identity}
$0+a=a+0=a$,
\item
\label{Z_axiom_addit_inverses}
$-a\in \Z$ and $a+(-a)=0$,
\item
\label{Z_axiom_assoc_mult}
$a\times (b\times c) = (a\times b) \times c$,
\item
\label{Z_axiom_comm_mult}
$a\times b = b\times a$
\item
\label{Z_axiom_mult_identity}
$a\times 1 = a$
\item
\label{Z_axiom_distrib}
$a\times (b + c) = (a\times b) + (a\times c)$
\item
\label{Z_axiom_additive_order}
if $a< b$ then $a+c < b+c$,
\item
\label{Z_axiom_mult_order}
if $0< a$ and $0<b$ then $0<ab$.
\item \textbf{Well-Ordering Axiom}
\label{well_orderering_axiom}
If $S$ is a nonempty subset of positive integers, and every element of
$S$ is $\ge 0$, then $S$ contains a smallest element.
\end{enumerate}
\end{definition}
\begin{comments}
We can derive all other familiar facts about the integers from the
above properties. We will not do that here, but will list a few,
and prove one.
\end{comments}
\begin{theorem}
The following properties hold for any $a,b,c\in \Z$:
\begin{enumerate}
\renewcommand{\labelenumi}{\theenumi}
\renewcommand{\theenumi}{(\alph{enumi})}
\item
\label{Z_additive_cancelation}
If $a+ b = a+ c$ then $b=c$.
\item \label{Z_mult_by_0}
$0\times a=a\times 0=0$.
\item \label{Z_neg_neg_is_pos}
$-(-a) = a$.
\item \label{Z_neg_is_associative}
$a\times (-b) = (-a)\times b=-(a\times b)$.
\item $(-a)\times (-b) = a\times b$.
\item $a\times (b-c) = a\times b -a\times c$.
\item If $a\times b = a\times c$, and $a\ne 0$, then $b=c$.
\item If $a < b$ and $0 < c$ then $ac < bc$.
\item If $a\ne 0$ and $a\times b=a\times c$ then $b=c$.
\item $-a = -1\times a$.
\item $1>0$.
\item \label{Z_mult_by_pos_preserves_ineq}
If $a < b$, and $c<0$ then $a\times c>b\times c$.
\item If $a<0$ and $b>0$ then $a\times b<0$. If $a<0$ and $b<0$ then
$a\times b>0$.
\item There does not exist $d\in \Z$ satisfying $a<d<a+ 1$.
\item \label{Z_archimedean_property}
There exists some $n\in \Z$ such that $n\times b>a$.
\end{enumerate}
\end{theorem}
\begin{proof}
We will prove just a couple of these properties. Allthough we are
not going to prove all of them here, we will assume them going
forward. In particular, we will assume when we prove
part~\ref{Z_mult_by_pos_preserves_ineq}, that the previous parts
have already been proven.
Part~\ref{Z_additive_cancelation}. Suppose $a+b=a+c$. Then $-a\in \Z$ by
property~\ref{Z_axiom_addit_inverses}. Adding $-a$ to both sides we
get $-a+(a+b) = -a+(a+c)$. Using
property~\ref{Z_axiom_assoc_addit} we have $(-a+a)+b = (-a+a)+c$.
Using property \ref{Z_axiom_comm_mult} we have $(a+(-a)) + b =
(a+(-a))+c$. Using property~\ref{Z_axiom_addit_inverses} we have $0+b
= 0+c$. Using property~\ref{Z_axiom_addit_identity} we have $b=c$.
Part~\ref{Z_mult_by_pos_preserves_ineq}. Suppose that $a<b$ and $c>0$. Add $-a$
to both sides to get $0 < b-a$. Multiply both sides by $c$ to get $0
< c(b-a)$. Finally, add $ac$ to both sides got get $ac < bc$.
\end{proof}
\begin{comments}
There are a couple of stylistic points to make about the previous
proofs. (1) It's very hard to prove things that are so ``obvious''
and ``elementary'' without skipping steps. When you are proving a
statement that is supposed to follow only from the most basic
definitions, a good rule of thumb is to make sure that you use
exactly one basic definition at each step. (2) Writing the proof of
part~\ref{Z_additive_cancelation} was a bit tedious, with all the
phrases like ``using property\ldots'', and with no simplifications
taking place until the next step. Not skipping the simplifications
was part of the point. Although the phrases seemed repetitious, the
goal in every proof should be to write complete sentences, with
references to which property is being used. As an alternative, one
could write a two column proof:
\begin{tcproof}{proof of part~\ref{Z_additive_cancelation}}
$a+b=a+c$ & Given\\
$-a\in \Z$ & \ref{Z_axiom_addit_inverses}\\
$-a+(a+b) = -a+(a+c)$ & adding $-a$ to both sides\\
$(-a+a)+b = (-a+a)+c$ & \ref{Z_axiom_assoc_addit}\\
$(a+(-a)) + b = (a+(-a))+c$. & \ref{Z_axiom_comm_mult}\\
$0+b = 0+c$. & \ref{Z_axiom_addit_inverses}\\
$b=c$ & \ref{Z_axiom_addit_identity}
\end{tcproof}
The advantages of a two-column proof are that we don't have to write
as many words, it's more obvious what the logical steps are, and the
justifications are clearly separated. However, two-column proofs
are annoying to read for anything that is longer than 5--10 steps, or
that would be clearer with some explanations. They are useful for the
simplest proofs, with the smallest steps.
My final comment is about the style of the proof given for
part~\ref{Z_mult_by_pos_preserves_ineq}. It's closer to the spirit of
how a student in this class should write proofs. It's similar to the
proof of part~\ref{Z_additive_cancelation}, but a small steps were
skipped, and instead of saying things like ``by Property Z23'' we just
said ``Add \dots to both sides to get''. The student should aim their
style somewhere between what we've done for
part~\ref{Z_additive_cancelation} and for
part~\ref{Z_mult_by_pos_preserves_ineq}, perhaps being closer to
part~\ref{Z_additive_cancelation} at the beginning of the semester,
and being closer to part~\ref{Z_mult_by_pos_preserves_ineq} by the end
of the semester.
\end{comments}
\begin{comments}
Now we turn to division. But our goal is to work entirely within the
integers, and so when we divide $5$ by $2$ we won't, ever, write
something like $\frac{5}{2}$ or $\frac{1}{2}$. We won't write
fractions, ever, as part of our formal work. We will of course allow
them informally when we're trying to understand what's going on. The
next example illustrates how to work with division without using
fractions.
\end{comments}
\begin{example}
Perform the division with remainder of $%(
11)\hspace{-.3em}\raisebox{\baselineskip}{$\begin{array}[t]{l}\\
\hline 1700\end{array}$}$. Double check your answer (using only
integers!).
\begin{solution}
$$%(
11)\hspace{-.3em}\raisebox{\baselineskip}{$\begin{array}[t]{r}
154 \rlap{\ R 6}\\\hline
1700\\
11\ \ \ \ \\\hline
600\, \\
55\ \ \,\\ \hline
50\ \,\\
44\ \\ \hline
6\
\end{array}$}
$$
One way to write this answer (the ``forbidden'' way) is:
$\frac{1700}{11} = 154 + \frac{6}{11}$. To double check this over
the integers, we can ``clear denominators'', i.e.\ multiply by $11$
to get
$$
1700 = 154\times 11 + 6.
$$
This equation can be verified (the right hand side is $1694 + 6 =
1700$), and the calculations are just over the integers.
\end{solution}
\end{example}
\begin{comments}
The following result states division with remainder over the
integers. The actual process of doing the division is not mentioned,
just the result. And, the result is stated without using fractions.
In essence, the way we double checked our work in the last example is
the result.
\end{comments}
\begin{theorem}[Division algorithm]
\label{theorem_division_alg_in_Z}
Let $a,b\in \Z$ with $b>0$. There exist unique elements $q,r\in \Z$
such that $a=qb + r$ with $0\le r < b$.
\end{theorem}
\endclass{Wednesday, September 3}
\begin{comments}
The numbers $q$ and $r$ are the familiar quotient and remainder that
appear in long division. Perhaps they will be more familiar written like
this
$$
\begin{array}{c@{}r@{\quad}c@{}c}
& q & & R \ r \\\cline{2-3}
b\ & \mbox{\large%(
)} \ a\ & &
\end{array}.
\qquad
\text{or}
\qquad
\frac{a}{b} = q + \frac{r}{b}.
$$
Here's a geometric way to picture this result. We partition the
number line into a sequence of intervals
$$
\ldots, [-4b, -3b),\ [-3b,-2b),\ [-2b,-b),\ [-b,0),\ [0,b),\
[b,2b),\ [2b,3b),\ldots\ .
$$
The statement of the theorem is equivalent to the fact that $a$ is
contained in a unique interval, $[qb,qb+b)$, at a unique distance $r$
from the left edge of the interval. The reader is invited to see how
the geometric description just given gets translated into the steps in
the proof below.
\end{comments}
\begin{proof}
The proof has two main parts: first we show that $q$ and $r$ exist,
then we show that they are unique.
Step 0: Define the set $S$:
\begin{align*}
S & = \{a-bx \mid q\in \Z,\ a-qp \ge0\}\\
& = \{\parbox{4in}{all numbers of the form $a-xb$ as $x$ ranges over
the integers and with $a-bx\ge 0$.}\}
\end{align*}
Our basic approach will be to apply the W.O.P.\ to the set $S$.
Step 1: Show that $S$ is nonempty. To do this we need to show that
some value of $x$ will make $a-bx \ge 0$. If $a\ge 0$ then let $x=0$.
Note that $a-bx = a \ge 0$ and so $a-bx\in S$. If $a<0$ then let
$x=a$. Note that $a-bx = a-b(a) = a(1-b)$. Note that $a$ is negative,
and $1-b$ is $\le 0$ (since $b>0$). Therefore, $a(1-b)\ge 0$, and so
$a-bx \in S$.
Step 2: Identify $q$ and $r$. Since $S$ is nonempty, and since it
contains only elements that are $\ge 0$, the W.O.P.\ shows that $S$
contains a smallest element: call it $r$. By definition of $S$ we
have that $r=a-bx$ for some $x\in \Z$: let $q=x$.
Step 3: We show that $0 \le r < b$. By construction we know that
$r\ge 0$. Suppose, for contradiction, that $r\ge b$. Then $r-b \ge
0$ and so $r-b= a-qb -b = a-(q+1)b \ge 0$. Therefore $r-b\in S$. But we
also have $r-b<r$ and this contradicts the construction of $r$ as the
smallest element of $S$.
Step 4: We show that $r$ and $q$ are unique. We do this by proving
the following statement: if $\tilde q$ and $\tilde r$ also satisfy the
conclusion of the theorem, then $\tilde q=q$ and $\tilde r =r$.
Suppose $a=\tilde qb + \tilde r$, with $0\le \tilde r < b$. Since
$0\le r$. One of the following must be true: $\tilde r \le r$ or
$r\le \tilde r$. Without loss of generality, we may assume that
$\tilde r \le r$. Then
\begin{align*}
r- \tilde r & \ge 0\\
qb - \tilde qb & \ge 0\\
( q - \tilde q)b & \ge 0\\
q - \tilde q & \ge 0
\end{align*}
On the other hand, we have
\begin{align*}
\tilde r & \ge 0 \\
-\tilde r & \le 0 \\
r & < b \\
r-\tilde r & < b \\
(q - \tilde q )b & < b \\
q - \tilde q & < 1
\end{align*}
So now we have
$$
0 \le \tilde q - q < 1.
$$
Since $\tilde q - q$ is an integer, and is between $0$ and $1$, it
must equal $0$. Therefore $q=\tilde q$ and $r=\tilde r$.
\end{proof}
\begin{example}
Use your calculator to apply the division algorithm and divide
$a=-5432$ by $b=234$. Double check your answer.
\begin{solution}
Here's what we enter, and what we get, using the calcultor:
\begin{TIscreen}
\in{-5432/234}
\out{-23.21367521}
\end{TIscreen}
It is a mistake to use $q=-23$, because $a$ is negative. We want the
integer to the \emph{left} of $-23.213\dots$, so we take $q=-24$.
Now we calculate $r$:
\begin{TIscreen}
\in{-5432-(-24*234)}
\out{184}
\end{TIscreen}
Thus $r=184$. Now we double check our answer:
\begin{TIscreen}
\in{234*(-24)+184}
\out{-5432}
\end{TIscreen}
\end{solution}
\end{example}
\section{Divisibility}
\label{section_eucl_alg_consequencens}
\begin{comments}
In this section we give the first result about the integers that is
not at the most basic level: what we state here is not quite obvious,
and can be proved using the definitions given in the previous
sections.
The main idea is to talk about division in the integers. As we do
this, the reader should take note that we always avoid working with
the rational numbers, i.e.\ fractions: we keep all statements strictly
within $\Z$ using addition and multiplication. Partly this is
stylistic, partly with a view towards working in other rings that are
not contained in something like $\Q$, partly as a matter of practice,
partly as a way to avoid making mistakes.
We start with the crucial definition (later stated for any ring).
\end{comments}
\begin{definition}
\label{def_divides_in_Z}
Let $a,b\in \Z$. We say that $a$ \define{divides} $b$ if $b=ac$ for
some $c\in Z$. We write this as $a|b$. Synonyms are ``$b$ is
divisible by $a$'', ``$b$ is a multiple of $a$'', ``$a$ is a factor of
$b$'', etc.
\end{definition}
\begin{comments}
Note that ``$a|b$'' is a statement about relationship between $a$ and
$b$. It does not say ``divide $a$ by $b$'' or ``divide $b$ by $a$''
or ``find $a\div b$'' or anything similar. You are not meant to
\emph{do} any calculation for ``$a|b$'' and in fact ``$a|b$'' is not
equal to a number.
\end{comments}
\begin{example}
Determine which of the following divide which others. Identify all
possible combinations.
$$
-2, -3, 2, 3, 4, 6, 10, 12, 15, 6+15
$$
\begin{solution}
We could write down a huge list of things like $2\notdiv 3$, $4\div
12$, etc. But since we have to figure out all possible combinations,
we might as well make a table:
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
& -2 & -3 & 2 & 3 & 4 & 6 & 10 & 12 & 15 & 6+15 \\ \hline
-2 & & & & & & & & & & \\ \hline
3 & & & & & & & & & & \\ \hline
2 & & & & & & & & & & \\ \hline
3 & & & & & & & & & & \\ \hline
4 & & & & & & & & & & \\ \hline
6 & & & & & & & & & & \\ \hline
10 & & & & & & & & & & \\ \hline
12 & & & & & & & & & & \\ \hline
15 & & & & & & & & & & \\ \hline
6+15 & & & & & & & & & & \\ \hline
\end{array}
$$
We'll write Y or N in each spot, so that $3|6$ is recorded with a Y in
the spot with $3$ to the left, and $6$ on top.
\endclass{Friday, September 5}
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|}
& -2 & -3 & 2 & 3 & 4 & 6 & 10 & 12 & 15 & 6+15 \\ \hline
-2 & Y & N & Y & N & Y & Y & Y & Y & N & N \\ \hline
3 & N & Y & N & Y & N & Y & N & Y & Y & Y \\ \hline
2 & Y & N & Y & N & Y & Y & Y & Y & N & N \\ \hline
3 & N & Y & N & Y & N & Y & N & Y & Y & Y \\ \hline
4 & N & N & N & N & Y & N & N & Y & N & N \\ \hline
6 & N & N & N & N & N & Y & Y & Y & N & N \\ \hline
10 & N & N & N & N & N & N & Y & N & N & N \\ \hline
12 & N & N & N & N & N & N & N & Y & N & N \\ \hline
15 & N & N & N & N & N & N & N & N & Y & N \\ \hline
6+15 & N & N & N & N & N & N & N & N & N & Y \\ \hline
\end{array}
$$
\end{solution}
\end{example}
\begin{comments}
Hopefully you looked for patterns in the previous example. Maybe you
wondered about why I wrote $6+15$ instead of $21$. The reason was to
help you think about the pieces in this number. So, if you have $3|6$
and $3|15$ what does that say about $3|(6+15)$? If you have $2|6$ and
$2\notdiv 15$ what does that say about $2|(6+15)$? Some of the
answers are recorded in the next lemma.
\end{comments}
\begin{lemma}
\label{lemma_basic_props_of_divides}
For all $a,b,c\in \Z$ the following properties hold.
\begin{enumerate}
\renewcommand{\labelenumi}{\theenumi}
\renewcommand{\theenumi}{(\alph{enumi})}
\item If $a|b$ and $b|c$, then $a|c$ (1.2\#3).
\item If $a|b$ then $a|bc$ (i.e.\ $a$ divides the product $bc$).
\item If $a|b$ and $a|c$ then $a|(b+c)$ (1.2\#4a).
\item If $a|b$ and $a\notdiv c$, then $a\notdiv(b+c)$.
\item If $a,b\ge 1$ and $a|b$ then $a\le b$.
\end{enumerate}
\end{lemma}
\endclass{Monday, September 8}
\begin{proof}
% Part (1). Suppose $a|b$ and $b|c$ and write $b=ax$ and $c=by$ for
% some $x,y\in \Z$. Then $c=az$ where $z=xy$, whence $a|c$.
%
Part (b). Suppose $a|b$. Then $b=ax$ for some $x\in \Z$. Then $bc
= axc$. Let $z=xc$. Then $z\in \Z$ and $bc = az$. Therefore
$a|bc$.
% Part (3). Suppose $a|b$ and $a|c$ and write $b=ax$ and $c=ay$. Then
% $b+c = az$ where $z=x+y$, whence $a|(b+c)$.
%
% Part (4). Suppose $a,b\ge 1$ with $a|b$ and write $b=ax$ for $x\in
% \Z$. Since $ax>0$ we have $x>0$, whence $x\ge 1$. Then $b-a = ax-a =
% a(x-1)$ with $a\in \N$ and $x-1\ge 0$. Therefore $a(x-1)\ge 0$ and
% $b\ge a$.
\end{proof}
\begin{definition}
Let $a,b\in \Z$, not both $0$. A \define{common divisor} of $a$ and
$b$ is a number that divides $a$ and divides $b$. We say that $d\in
\Z$ is a \define{greatest common divisor} of $a$ and $b$ if $d$ is a
common divisor of $a$ and $b$ and $d$ is $\ge$ any other common
divisor of $a$ and $b$. If $\gcd(a,b)=1$ then we say that $a$ and
$b$ are \define{relatively prime}.
\end{definition}
\begin{comments}
The next result is quite surprising in many ways. It has all sorts of
implications for common divisors, and work in modular numbers
(Chapter~\ref{chapter_modular_numbers}). And, it provides the main
reason that unique factorization holds in $\Z$. Note: the statement
is made completely inside the integers, and without the use of
fractions.
\end{comments}
\begin{theorem}[GCD equals $\Z$-linear combination]
\label{theorem:gcd_equals_Z_lin_comb}
Let $a,b\in \Z$, not both $0$. Then
$$
\gcd(a,b)= na+mb
$$
where (1) $n,m\in \Z$, (2) $na+mb\ge0$, and (3) $na+mb$ is the
smallest number satisfying (1) and (2). In other words, $\gcd(a,b)$
is the smallest positive $\Z$-linear combination of $a$ and $b$.
\end{theorem}
\begin{example}
Through trial and error, show how to write $\gcd(15,55)$ as a linear
combination of $15$ and $55$.
\begin{solution}
We can easily see that $\gcd(15,55)=5$. It's ``clear'' that we should
subtract $15$ from $55$.
\begin{align*}
55 - 15 & = 40\\
55 - 2\times 15& = 25\\
55 - 3\times 15 & = 10
\end{align*}
This got us close to $5$ but we can't keep going because the next step
would have a negative number. So, we try using a multple of $55$:
\begin{align*}
2\times 55 - 15 & = 95\\
2\times 55 - 2\times 15 & = 80\\
2\times 55 - 3\times 15 & = 65\\
2\times 55 - 4\times 15 & = 50\\
2\times 55 - 5\times 15 & = 35\\
2\times 55 - 6\times 15 & = 20\\
2\times 55 - 7\times 15 & = 5
\end{align*}
Thus, our answer is
$$
5 = 2\times 55 - 7\times 15.
$$
\end{solution}
\end{example}
\begin{comments}
The previous example gives a hint as to the technique of proof we'll
use in the theorem. We looked at subtracting one number from another,
and we looked at how small we could make the result, while still
keeping it positive. This should suggest the W.O.P.
\end{comments}
\begin{proof}
Step 0: Define the set $S$:
\begin{align*}
S & = \{xa + yb \mid m,n\in \Z,\ xa+ny >0\}\\
& = \left\{\parbox{4in}{all numbers of the form $xa+yb$ where this is
positive and $x$ and $y$ are integers.}\right\}
\end{align*}
Our basic approach will be to apply the W.O.P.\ to the set $S$.
Step 1: Show that $S$ is nonempty. We may assume that $a\ne 0$. If
$a>0$ then $a = 1\cdot a + 0 \cdot b \in S$. If $a<0$ then $-a =
-1\cdot a + 0\cdot b \in S$. This shows that $S\ne \emptyset$.
Step 2: Identify $d=\gcd(a,b)$. Since $S$ is nonempty, and since all
the elements of $S$ are positive, by definition, the W.O.P.\ shows
that $S$ contains a smallest element, $d$. By definition of $S$, we
can write $d = ma+nb$ for some $m,n\in \Z$.
Step 3: Show that $d$ is a common divisor of $a$ and $b$. Suppose for
contradiction that $d$ does not divide $a$. Apply the division
algorithm (Theorem~\ref{theorem_division_alg_in_Z}) and let $a=qd+r$
with $0\le r <d$. Since $d$ does not divide $a$, we see that $r>0$.
Then
$$
0< r = a-qd = a-q(ma+nb) = (1-qm)a + (-qn)b <d
$$
This gives a $\Z$-linear combination of $a$ and $b$ which is positive
and $<d$, a contradiction.
Step 4: Show that $d\ge $ any other common divisor of $a$ and $b$.
Let $\tilde d$ be a common divisor of $a$ and $b$. Let $a=\tilde
d\cdot r$ and $b=\tilde d \cdot s$. Then $d=ma+nb = m\tilde d r +
n\tilde d s = (mr+ns) \tilde d$. Since $d$ is a multiple of $\tilde
d$, we see that $d \ge \tilde d$.
\end{proof}
\endclass{Wednesday, September 10}
\begin{theorem}
\label{theorem:gcd_equals_1_implies_divides_other_factor}
If $a|bc$ and $\gcd(a,b)=1$, then $a|c$.
\end{theorem}
\begin{proof}
Suppose $a|bc$ and $\gcd(a,b)=1$. Apply
Theorem~\ref{theorem:gcd_equals_Z_lin_comb} to write the gcd as a
linear combination and get
$$
1 = ma + nb
$$
for some $m,n\in \Z$. Multiply both sides of this equation by $c$ to
get
$$
c = mac + nbc.
$$
Since $a|bc$ we can write $bc=ax$ for some $x\in \Z$. Therefore, the
previous equation becomes
$$
c = mac + nax.
$$
Factoring, we get
$$
c = (mc+nx)a.
$$
Let $z= mc + nx$, then $z\in \Z$ and
$$
c=za
$$
which means $a|c$.
\end{proof}
\section{Unique factorization and the integers}
\begin{comments}
In this section we study the final, important property of the
integers: that they have unique factorization. You probably take
for granted that each integer can be uniquely factored into primes,
but this property is both subtle and important. Subtle, as
witnessed by the fact that for 2000 years the result existed in a
limbo state: pretty well assumed, and pretty well proven, but not
100\% explicit. It was Gauss who finally gave a statement that we
would accept as completely precise (see \cite{} for an article about
exactly what Euclid and Gauss stated). Important for some
applications that we'll mention later, as well as for advanced
research in topics such as Fermat's Last Theorem. In fact, it was
exactly the failure of unique factorization to hold in a different
kind of number system that doomed some mathematician's efforts to
prove Fermat's Last Theorem, and through efforts of others led to
the invention of parts of modern algebra. (See \emph{Algebraic
Number Theory} by Edwards for more of this history and
mathematics.)
\end{comments}
\begin{definition}
Let $p\in \Z$ with $p\ne 0, \pm 1$. We say that $p$ is
\define{prime} if the only integers that divide $p$ are $\pm 1$ and
$\pm p$.
\end{definition}
\begin{definition}
Let $n\in \Z$. We say that $n$ is a product of primes if (1) $n$ is
prime or (2) $n=p_1\dots p_r$ for some primes $p_1$, \dots, $p_r$.
\end{definition}
\begin{example}
Write $24255$ as a product of primes. How do you know you'll ever finish?
\begin{solution}
It's easy to see that $24255$ is divisible by $5$ so we start by
factoring out $5$:
$$
24255 = 5\times 4851.
$$
Now $4851$ is divisible by $3$:
$$
24255 = 5\times 4851 = 5\times 3 \times 1617.
$$
Now $1617$ is divisible by $3$ again:
$$
24255 = 5\times 3 \times 1617 = 5\times 3 \times 3\times 539.
$$
Now $539$ is divisible by $7$:
$$
24255 = 5\times 3 \times 3\times 539 = 5\times 3 \times 3\times 7\times 77.
$$
Finally, $77$ is divisible by $7$:
$$
24255 = 5\times 3 \times 3\times 7\times 77 = 5\times 3 \times 3\times 7\times 7\times 11.
$$
We knew that this process would eventually finish because the part we
hadn't factored yet kept getting smaller. It can't get smaller
forever because the unfactored part is always a positive integer.
\end{solution}
\end{example}
\begin{comments}
The point of the previous example is to think about how we would prove
the following theorem.
\end{comments}
\begin{theorem}[Fundamental Theorem of Arithmetic I: Existence of
factorization]
\label{theorem_existence_factorization_in_Z}
Let $n\in \Z$ with $n\ne 0, \pm 1$. Then we can write $n$ as a
product of primes.
\end{theorem}
\begin{proof}
Step 0: suppose we have proven it for $n\ge 2$. Then we are done: if
$n\le -2$ then we can apply the theorem to $-n$ to get $-n =
p_1\cdots,p_r$, and then conclude $n = (-p_1)p_2\cdots p_r$.
Step 1: Assume $n\ge 2$ and assume \emph{for contradiction} that $n$
cannot be written as a product of primes.
Step 2: Define the set $S$:
$$
S = \{x\in\Z \mid x\ge2,\ x\ne \text{ a product of primes}\}.
$$
Step 3: Show that $S$ is nonempty. We have assumed for contradiction
that $n\ge 2$ exists such that $n$ is not equal to a product a primes.
Thus $n\in S$.
Step 4: Identify minimal element of $S$. Since $S$ is nonempty, and
since all the elements of $S$ are positive by definition, the W.O.P.\
shows that $S$ contains a smallest element $m$.
Step 5: Get a contradiction. By definition, $m\ge
2$ and $m$ cannot be written as a product of primes. Therefore $m$ is
not prime. Therefore $m=ab$ for some factors $a$, $b$ with $a,b\ne
\pm 1, \pm m$. Since $m$ is positive we may choose $a$ and $b$ to be
positive, so $1 < a,b<m$. Therefore both $a$ and $b$ are smaller than
$m$. Since $m$ is the smallest element of $S$, this means that $a$
and $b$ are not in $S$. By definition of $S$ this means that $a$ and
$b$ can be written as a product of primes:
$$
a = p_1\cdots p_r,\quad
b = q_1\cdots q_s,
$$
where all the $p_i$ and $q_j$ are prime.
Therefore
$$
m = ab = p_1\cdots p_r \cdot q_1\cdots q_s.
$$
But this means that $m$ is a product of primes, a contradiction.
\end{proof}
\begin{comments}
Note that the previous proof was spread out, broken into multiple
steps, and explained at some length. This is done on purpose with
the hope that every reader can follow every step. However, once the
reader has understood the proof, or if the reader is already more
experienced in these sorts of proofs, the argument can be shortened,
and this may make it easier to remember or follow. Here's a
shortened version:
\begin{proof}
It suffices to prove the result for positive numbers, since
otherwise we can apply the theorem to $-n$. Suppose for
contradiction that there exists $n\ge 2$ such that $n$ cannot be
written as a product of primes. Then the set
$$
S = \{x\in\Z \mid x\ge2,\ x\ne \text{ a product of primes}\}
$$
is nonempty. Apply the W.O.P.\ and let $m$ be the smallest element of
$S$. Then $m$ is not prime and so we can factor $m=ab$, where
$1<a,b<m$. Then $a,b\not\in S$ and so we can write $a$ and $b$ as
products of primes
$$
a = p_1\cdots p_r,\quad
b = q_1\cdots q_s.
$$
Therefore
$$
m = ab = p_1\cdots p_r \cdot q_1\cdots q_s,
$$
which is a contradiction.
\end{proof}
Perhaps, for amusement, or maybe as a useful exercise, it helps to see
an even shorter version (I would point out that such a version is
\emph{not} very nice to give to someone else to read).
\begin{proof}
If $n$ is negative, multiply by $-1$. Suppose that $n\ge 2$ is not
a product of primes, and that it is the smallest such. Since $n$ is
not prime we can write $n=ab$ where $1< a, b < n$. Writing $a$ and
$b$ as a product of primes gives that $n$ is as well, a
contradiction.
\end{proof}
To illustrate an extremism, we give a hiku version (it has 5, 7, and 5
syllabules, when read correctly):
\begin{proof}
Make $n$ positive.\\
Factors are smaller, product\\
of primes. So is $n$.
\end{proof}
\end{comments}
\begin{comments}
We turn now to uniqueness of factorization. Since we are working
over the integers instead of just $\N$, uniqueness will always be up
to multples of $+1$ or $-1$. This even shows up in the next lemma.
\end{comments}
\begin{lemma}
\label{lemma:divide_each_other_equal_up_to_unit}
If $a$ and $b$ are any two integers with $a|b$ and $b|a$ then $a=\pm
b$.
\end{lemma}
\begin{proof}
Homework.
\end{proof}
\begin{comments}
The following result is the main ``engine'' in the uniqueness of
factorization theorem that is coming up.
\end{comments}
\begin{theorem}[Euclid's Lemma]
\label{theorem:Euclids_lemma}
Let $p\in \Z$ with $p\ne 0, \pm 1$. Then $p$ is prime if and only if
it satisfies this property:
\begin{align}
\tag{$*$}
\forall a,b\in \Z,\text{ if } p|ab \text{ then } p|a \text{ or } p|b
\end{align}
\end{theorem}
\begin{proof}
\forwards. Suppose $p$ is prime. We need to prove the $p$ satisfies
$(*)$. So, let $p|ab$. We need to prove that $p|a$ or $p|b$. If
$p|a$, then we are done. Otherwise, suppose $p\notdiv a$.
Since $p$ is prime, we have $\gcd(a,p)$ equal $1$ or $p$. Since
$p\notdiv a$ we have $\gcd(a,p)=1$. Apply
Theorem~\ref{theorem:gcd_equals_Z_lin_comb} and write $1=ma + np$.
Multiply both sides of this equation by $b$ to get $b=mab + npb$.
Then $p|npb$ (since $p|p$) and $p|mab$ (since $p|ab$). Therefore
$p|(mab + npb)$, whence $p|b$.
\endclass{Friday, September 12}
\backwards. Suppose $p$ satisfies $(*)$. Let $d|p$. Then $p=dx$ for
some $x\in \Z$. Since $p|p$ we have $p|dx$. By property ($*$) we
have that $p|d$ or $p|x$. If $p|d$ then $d=\pm p$ by
Lemma~\ref{lemma:divide_each_other_equal_up_to_unit}. If $p|x$ then
$x=pz$ for some $z\in \Z$. Then $p=dx=dpz$. Cancelling $p$ from both
side we see $1=dz$. Thus $d=\pm 1$. Therefore, any integer which
divides $p$ must equal $\pm 1$ or $\pm p$, and so $p$ is prime.
\end{proof}
\begin{comments}
\begin{proof}
The first part of the previous theorem can be proven directly, without
using Theorem~\ref{theorem:gcd_equals_1_implies_divides_other_factor}.
Suppose $p$ is prime. We need to prove the following: if $p|ab$
then $p|a$ or $p|b$. Suppose $p|ab$. We need to prove that $p|a$
or $p|b$. Suppose $p\notdiv a$. Let $d=\gcd(p,a)$. Since $p$ is
prime we have that $d$ equals $1$ or $p$. Since $d|a$, and
$p\notdiv a$, we see that $d\ne p$, and so $d=1$. Now
Theorem~\ref{theorem:gcd_equals_1_implies_divides_other_factor}
shows that $p|b$.
\end{proof}
\end{comments}
\begin{cor}
Let $p$ be prime and suppose that $p|a_1a_2\cdots a_r$. Then
$p|a_i$ for some~$i$.
\end{cor}
\begin{proof}
Induct on $r$.
\end{proof}
\begin{example}
How many ways can you write $-30$ as a product of primes?
\begin{solution}
The prime factors are easily found
$$
-300 = -2\times 3 \times 5.
$$
But there are \emph{lots} of ways we can write this:
\begin{align*}
-30
& = (-2)\times 3 \times 5\\
& = (-2)\times 5\times 3\\
& = (-3)\times 2\times 5\\
& \ \vdots\\
& = 2\times (-3) \times 5\\
& = 2\times \times (-5)\\
& \ \vdots\\
& = (-5)\times (-2)\times (-3)\\
& = (-5)\times (-3)\times (-2)
\end{align*}
(Why not try to calculate how many ways we rearrange the factors and
the negative signs?)
But of course, most of the time we don't view the different ways of
writing these prime factors as making any real difference: we ignore
the differences shown here.
\end{solution}
\end{example}
\begin{comments}
Nowe we are ready to state and prove the uniqueness part of prime
factorization.
\end{comments}
\begin{theorem}[Fundamental Theorem of Arithmetic II: Uniqueness of factorization]
\label{theorem_uniqueness_factorization_in_Z}
Let $n\in \Z$, $n\ne 0,\pm1$. Then the prime factorization given by
Theorem~\ref{theorem_existence_factorization_in_Z} is unique. In
other words, if
$$
n= p_1 \cdots p_r = q_1 \cdots q_s
$$
where each $p_i$ and each $q_i$ is a prime, then $r=s$ and, if
necessary, we may rearrange the factors on one side, so that $p_i =
\pm q_i$ for each $i$.
\end{theorem}
\begin{comments}
Note that if we require that $n$, as well as each $p_i$ and $q_i$ are
required to be in $\N$, as opposed to $\Z$, then we can remove the
``$\pm$'' in the last line of this theorem.
\end{comments}
\begin{proof}
Step 0: Set up an index for induction. By
Theorem~\ref{theorem_existence_factorization_in_Z}, we know that $n$
has a prime factorization. Let $r$ be the number of factors which
appear in this factorization. In other words, $r$ is the number of
primes which it is possible to write $n$ as a product of. We induct
on $r$.
Step 1: Base case, $r=1$. It is possible to write $n$ as a product
of $1$ prime, so we have $n=p_1$. Suppose we can also write
$n=q_1\cdots q_s$. Then $p=q_1\cdots q_s$. Since $p$ is prime this
implies that $s=1$ and $q_1=p_1$.
Step 2: Induction hypothesis. Suppose now that the theorem has been
proven for all $r$ in a range $\{1,\dots, k\}$. In other words, the
uniqueness statement holds for any number than equals a single
prime, or a product of two primes, or a product of three primes, or
\dots, a product of $k$ primes.
Step 3: Induction step. Let $r=k+1$. Then it is possible to write
$n$ as a product of $k+1$ primes, so we have
$$
n=p_1\cdots p_{k+1}.
$$
Suppose we can also write $n=q_1\cdots q_s$. Then $p_1|n$ and so
$p_1|q_1\cdots q_s$, and so by the corollary to Lemma~\ref{theorem:Euclids_lemma}
we have that $p_1$ divides some $q_i$. Rerrange the factors if
necessary so that $p_1|q_1$. Then $p_1=\pm q_1$. Then we can cancel
and get $p_2\cdots p_{k+1} = \pm q_2 \cdots q_s$. Let $\tilde n =
p_2\cdots p_{k+1}$. Then $\tilde n$ has $k$ prime factors.
Therefore the uniqueness statement holds for $\tilde n$. Therefore,
after rearranging the factors we can conclude $p_2 = \pm q_2$, $p_3 =
\pm q_3$, \dots, $p_{k+1} = \pm q_s$. Also, we have the number of
factors in $p_2\cdots p_{k+1}$ equals the number of factors in
$q_2\cdots q_s$, i.e.\ $k = s-1$, and so $r-1=s-1$ and $r=s$.
\end{proof}
\subsection{Applications}
\begin{comments}
In this subsection we allude to some important applications that come
later, and explicitly give a somewhat whimsical application in the
meantime. Perhaps though we should start by clarifying the word
``application''. In most people's minds, if we say that $X$ has an
application, it means that $X$ can be used in practical sense, or to
accomplish something concrete. In mathematics, it simply means that
$X$ implies $Y$ where $Y$ has some sort of value, such as being well
known, or interesting, or important, etc. So, the applications that
come later are of this type: mathematical facts that have some value.
The application that comes presently is concrete, but not exactly
realistic on its own terms.
Unique factorization of the integers is what makes the following
mathematical facts work:
\begin{itemize}
\item The fact that every rational number $\frac{a}{b}$ can be
written, uniquely, in reduced form, i.e.\ wwith $a$ and $b$ having
no common factors,
\item The fact that $\sqrt{2}$ is irrational,
\item The fact that we can use an alternative notation for integers,
writing them as products of primes,
\item The fact that we can define and/or calculate various functions
such as $\gcd$, $\lcm$, and others, on the integers in terms
of their product of prime notation.
\end{itemize}
Now we give our whimsical, or not exactly realistic, application.
\end{comments}
\handoutpagebreak
\begin{definition}
The \define{prime cipher} encrypts text as follows:
\begin{itemize}
\item Encode letters as prime numbers as follows:
\begin{multicols}{7}
a=2\\ b=3\\ c=5\\ d=7\\ e=11\\ f=13\\ g=17\\ h=19\\ i=23\\ j=29\\
k=31\\ l=37\\ m=41\\ n=43\\ o=47\\ p=53\\ q=59\\ r=61\\ s=67\\ t=71\\
u=73\\ v=79\\ w=83\\ x=89\\ y=97\\ z=101
\end{multicols}
\item Take a message in plain text, remove the spaces, break the
letters up into blocks of 3, or as long as possible without
including a repeated letter.
\item For each block of text replace each letter with it's prime, and
raise the prime to the $n$ power where $n$ is the position of the
letter within the block.
\item For each block, multiply the primes, including their powers,
together. The resulting number is the encrypted version of the
block, and the list of all blocks is the encrypted version of the
message.
\item To decrypt you factor each block, put each prime in the
correct position using the power, and then turn the primes back into
letters.
\end{itemize}
\end{definition}
\begin{example}
Encrypt the message: ``{\tt attack at dawn}''.
\begin{solution}
\begin{center}
\begin{tabular}{cccccc}
\multicolumn{5}{c}{\tt attackatdawn} & remove spaces\\
{\tt at } & {\tt tac} & {\tt kat} & {\tt daw} & {\tt n} & break into blocks\\
$2\times 71^2$ & $ 71\times 2^2 \times 5^3$ & $ 31 \times 2^2 \times 71^3$ &
$ 7\times 2^2\times 83^3$ & $43$ & encode in prime powers\\
10082 & 35500 & 44380864 & 16010036 & 43 & multply out
\end{tabular}
\end{center}
So, the final encrypted message is
$$
10082\quad 35500 \quad 44380864 \quad 16010036 \quad 43
$$
\end{solution}
\end{example}
\handoutpagebreak
\endclass{Monday, September 15}
\begin{comments}
Figure~\ref{figure:hungerfords_factor_program} shows a TI program to
find the prime factors of numbers (the program is from the extra
resources material for the Hungerford textbook, available at
cengagebrain.com).
\begin{figure}
\caption{Hungerford's Factor program}
\label{figure:hungerfords_factor_program}
\begin{multicols}{2}
\renewcommand{\to}{\ding{212}}
{\tt
:ClrHome\\
:Prompt N\\
:1\to I\\
:2\to D\\
:Lbl 1\\
:\raisebox{0.5ex}{$\sqrt{}$}\!(N)\to C\\
:If D$>$C\\
:Goto 2\\
:If I>6\\
:Goto 3\\
:If fPart(N/D)=0\\
:Goto 4\\
:If D=2\\
:Goto 5\\
:D+2\to D\\
:Goto 1\\
:Stop\\
:Lbl 4\\
:Disp D\\
:I+1\to I\\
:N/D\to N\\
:If N=1\\
:Stop\\
:Goto 1\\
:Lbl 2\\
:Disp N\\
:Stop\\
:Lbl 3\\
:Disp \verb$"CONTINUES"$\\
:Pause\\
:1\to I\\
:ClrHome\\
:Goto 1\\
:Lbl 5\\
:3\to D\\
:Goto 1}
\end{multicols}
\end{figure}
\end{comments}
\iffalse
My explanation of the above code:
Let $N$ = number to factor.
Let $I$ = 1 = number of factors displayed on screen.
Let $D$ =2 be the divisor we are testing.
Process 1:
If $D>\sqrt{N}$ then print $N$ and stop.
If $I>6$ then reset, clear screen and repeat Process 1.
If $D|N$ then print $D$, increase $I$, let $N=N/D$, and repeat process 1.
If $D=2$, let $D=3$ and repeat process 1.
Otherwise, let $D=D+2$ and repeat process 1.
note: this will only print prime D's because by the time the loop
gets to a composite D =a b, it will already have tested for
divisibilty by a and by by.
\fi
\begin{example}
Decrypt the following message.
$$
13451794\quad 22471119\quad 772650766\quad 1445166215
$$
\begin{solution}
The hard part is finding the factors. Start with easy primes such as
$2$, $3$, $5$, etc.
$$
13451794 = 2 \times 6725897.
$$
Now we know the other factors are not even. So there is only one
factor of $2$, and the other factors must be of the form $p^2$ or
$p^3$. We divide $6725897$ by $3$, by $5$, by $11$, by $13$ and then
by $17$. Since $17$ works, we divide by $17^2$, and again by $17^3$
$$
6725897 = 17^2\times 1369.
$$
Now we divide $23273$ by $19$, $23$, $29$, $31$ and $37$. It turns
out that $37^2 = 1369$. So we have our first decryption:
$$
13451794 = 2 \times 17^3 \times 37^2
\longrightarrow
{\tt alg}.
$$
Now we repeat this work for the other blocks:
\begin{center}
\begin{tabular}{cccc}
22471119 & 772650766 & 1445166215 & what we start with\\
$3^2 \times 11 \times 61^3$ & $2\times 47^3 \times 61^2$ & $5\times 31^2\times 67^3$ & a lot of work!\\
ebr & aro & cks
\end{tabular}
\end{center}
So our plain text message is
\begin{center}
\tt
alg ebr aro cks\\
algebra rocks
\end{center}
\end{solution}
\end{example}
\handoutpagebreak
\chapter{Congruence in \texorpdfstring{$\mathbb{Z}$}{Z} and Modular Arithmetic}
\label{chapter_modular_numbers}
\begin{comments}
In this chapter we learn about one of the most important types of
rings, the modular numbers. These numbers are centrally important in
ring theory, group theory and number theory. They also have a huge
number of important applications from check digits, to bar codes, and
public key encryption. Given all this, their most suprising property
might be that they are quite simple.
People think about modular numbers in two ways: one that is
conceptually simple, but somewhat difficult to prove things about; and
a second way that is conceptually harder, but that is easier to prove
things about. The second approach is what is almost always used in
textbooks, because it yields the best proofs, and generalizes to other
settings. We will follow this approach.
\end{comments}
\section{Congruence and Congruence Classes}
% Note: we do not add and multiply classes in this section. We simply
% define them.
\begin{definition}
Let $n\in\Z$, $n\ge 2$. For all $a,b\in \Z$, if $n|(a-b)$ then we
write $a\equiv b \pmod n$ and we say that $a$ is \define{congruent} to
$b$ modulo $n$. If the value of $n$ is clear in context, then we
will write just $a\equiv b$, dropping ``$(\bmod\ n)$''.
\end{definition}
\begin{example}
Identify for each combinition of $a$, $b$ and $n$ whether it's true
or false that $a\equiv b \pmod n$: % n=5,6,7
\begin{align*}
(a,b) & \in \left\{\parbox{3in}{$(-4, 6)$,\quad
$(4, 4)$,\quad
$(4, 5)$,\quad
$(4, 17)$,\quad
$(4, 2)$,\quad
$(5, 17)$,\quad
$(5, 25)$,\quad
$(6, 21)$,\quad
$(17, 5)$}\right\}
\\
n & \in \{5,6,7\}
\end{align*}
\begin{solution}
We will organize our answers in the table shown in Figure~\ref{figure:table_for_answers_to_example}
\begin{figure}[htp]
\caption{Table for answers to example}
\label{figure:table_for_answers_to_example}
$$
\renewcommand{\arraystretch}{2.5}
\begin{array}{c|c|c|c|}
a\text{ and } b & n=5 & n=6 & n=10\\ \hline
-4, 6 & \hspace*{1.5in} & \hspace*{1.5in} & \hspace*{1.5in} \\ \hline
4, 4 & & & \\ \hline
4, 5 & & & \\ \hline
4, 17 & & & \\ \hline
4, 25 & & & \\ \hline
5, 17 & & & \\ \hline
5, 25 & & & \\ \hline
6, 21 & & & \\ \hline
17, 5 & & & \\ \hline
\end{array}
$$
\end{figure}
The resulting work is shown in Figure~\ref{figure:answers_to_example}
\begin{figure}[htp]
\caption{Answers to example}
\label{figure:answers_to_example}
$$
\begin{array}{c|c|c|c|}
a\text{ and } b & n=5 & n=6 & n=7\\ \hline
-4, 6
& \begin{array}{c}5\divq(-4-6)\\ 5\divq-10\\ T\end{array}
& \begin{array}{c}6\divq(-4-6)\\ 6\divq-10\\ F\end{array}
& \begin{array}{c}10\divq(-4-6)\\ 10\divq-10\\ T\end{array}
\\ \hline
4, 4
& \begin{array}{c}5\divq(4-4)\\ 5\divq0\\ T\end{array}
& \begin{array}{c}6\divq(4-4)\\ 6\divq0\\ T\end{array}
& \begin{array}{c}10\divq(4-4)\\ 10\divq0\\ T\end{array}
\\ \hline
4, 5
& \begin{array}{c}5\divq(4-5)\\ 5\divq-1\\ F\end{array}
& \begin{array}{c}6\divq(4-5)\\ 6\divq-1\\ F\end{array}
& \begin{array}{c}10\divq(4-5)\\ 10\divq-1\\ F\end{array}
\\ \hline
4, 17
& \begin{array}{c}5\divq(4-17)\\ 5\divq-13\\ F\end{array}
& \begin{array}{c}6\divq(4-17)\\ 6\divq-13\\ F\end{array}
& \begin{array}{c}10\divq(4-17)\\ 10\divq-13\\ F\end{array}
\\ \hline
4, 25
& \begin{array}{c}5\divq(4-25)\\ 5\divq-21\\ F\end{array}
& \begin{array}{c}6\divq(4-25)\\ 6\divq-21\\ F\end{array}
& \begin{array}{c}10\divq(4-25)\\ 10\divq-21\\ T\end{array}
\\ \hline
5, 17
& \begin{array}{c}5\divq(5-17)\\ 5\divq-12\\ F\end{array}
& \begin{array}{c}6\divq(5-17)\\ 6\divq-12\\ T\end{array}
& \begin{array}{c}10\divq(5-17)\\ 10\divq-12\\ F\end{array}
\\ \hline
5, 25
& \begin{array}{c}5\divq(5-25)\\ 5\divq-20\\ T\end{array}
& \begin{array}{c}6\divq(5-25)\\ 6\divq-20\\ F\end{array}
& \begin{array}{c}10\divq(5-25)\\ 10\divq-20\\ T\end{array}
\\ \hline
6, 21
& \begin{array}{c}5\divq(6-21)\\ 5\divq-15\\ T\end{array}
& \begin{array}{c}6\divq(6-21)\\ 6\divq-15\\ F\end{array}
& \begin{array}{c}10\divq(6-21)\\ 10\divq-15\\ F\end{array}
\\ \hline
17, 5
& \begin{array}{c}5\divq(17-5)\\ 5\divq 12\\ F\end{array}
& \begin{array}{c}6\divq(17-5)\\ 6\divq 12\\ T\end{array}
& \begin{array}{c}10\divq(17-5)\\ 10\divq 12\\ F\end{array}
\\ \hline
\end{array}
$$
\end{figure}
\end{solution}
\end{example}
\begin{comments}
Warning: there is a similar, but slightly different meaning for the
notation for $\bmod n$. We have used it here as it appears in
almost all math textbooks; it goes along with $\equiv$ and two
numbers $a$ and $b$. However, a very similar, but slightly
different meaning is also common: $\bmod$ is used as a function so
that $a \bmod n$ means ``give me the smallest number $r\ge0$ such
that $a\equiv r \pmod n$.'' It turns out that $r$ in this case is
the remainder of $a$ divided by $n$.
The notation is not ambiguous if only one number is given, as in
``the answer is $235 \bmod 11$''. This always means take the
remainder of $235$ after division by $11$. The notation is not
ambiguous if two numbers are given, both of which are known, as in
``we see that $290 \equiv 235 \mod 11$''. The one case where
ambiguity can occur is where one number is known, but not the other,
for instance ``let $x\equiv 15 \pmod 6$''. Here, one could mean
$x=3$, but it would also be correct to allow $x = 45$.
In any case, the notation $\equiv$ was introduced by Gauss. It was
probably chosen as something that looks like ``$=$'', and indeed
$\equiv$ works similarly to $=$, as the next few results show.
\end{comments}
\begin{theorem}[Congruence is an Equivalence Relation]
Let $n\in\Z$, $n\ge 1$. The relation $a\equiv b \pmod n$ is an
equivalence relation. In other words, $\forall a,b,c\in \Z$, we
have the following:
\begin{enumerate}
\item $a\equiv a \pmod n$ (reflexive property),
\item if $a\equiv b \pmod n$, then $b\equiv a \pmod n$ (symmetric
property),
\item if $a\equiv b\pmod n$, and $b\equiv c \pmod n$, then $a\equiv
c\pmod n$ (transitive property).
\end{enumerate}
\end{theorem}
\begin{proof}
I will write these proofs as calculations, althought it pains me to
do so, for in almost all cases calculations should be mixed with
words that clarify, explain and motivate. But in this case, the
calculations are so simple that I think the student may understand
them better without too much extra verbiage.
\begin{enumerate}
\item
\begin{align*}
a & \stackrel{?}{\equiv} a \pmod n \\
\iff n & \divq (a-a)\\
\iff n & \divq 0\quad \checkmark
\end{align*}
In other words, $a\equiv a\pmod n$ is equivalent to $n|0$, and $n|0$
is true.
\item
\begin{align*}
a & \equiv b \pmod n \\
& \Rightarrow n | (a-b) \\
& \Rightarrow a-b = nx,\quad x\in \Z \\
& \Rightarrow b-a = n(-x),\quad -x\in \Z \\
& \Rightarrow n | (b-a) \\
& \Rightarrow b \equiv a \pmod n
\end{align*}
\item
$$
\begin{array}{rc@{\quad}l}
\left.\begin{array}{r@{\ }l@{\quad}c@{\quad}r@{\ }l}
a & \equiv b\pmod n & \Rightarrow & n & |(a-b)\\
b &\equiv c \pmod n & \Rightarrow & n & |(b-c)
\end{array}
\right\}
& \Rightarrow & n\left|\left(\raisebox{0ex}[1.25\height]{$(a-b)+(b-c)$}\right)\right.\\
& \Rightarrow & n|(a-c)\\
& \Rightarrow &a\equiv c \pmod n
\end{array}
$$
\end{enumerate}
\end{proof}
\begin{theorem}
\label{theorem:arithmetic_modulars_well_defined}
Let $n\in \Z$ with $n\ge 1$. Let $a\equiv b \pmod n$ and $c\equiv
d\pmod n$. Then the following hold:
\begin{enumerate}
\item $a+c \equiv b+d\pmod n$,
\item $ac\equiv bd\pmod n$.
\end{enumerate}
\end{theorem}
\begin{proof}
The proofs are again mainly calculations. In both parts we assume
that $a\equiv b \pmod n$ and $c\equiv d\pmod n$.
\begin{enumerate}
\item
A sequence of calculations shows that
$$
\begin{array}{rc@{\quad}l}
\left.\begin{array}{r@{\ }l@{\quad}c@{\quad}r@{\ }l}
a & \equiv b\pmod n & \Rightarrow & n & |(a-b)\\
c &\equiv d \pmod n & \Rightarrow & n & |(c-d)
\end{array}
\right\}
& \Rightarrow & n\left|\left(\raisebox{0ex}[1.25\height]{$(a-b)+(c-d)$}\right)\right.\\
& \Rightarrow & n\left|\left(\raisebox{0ex}[1.25\height]{$(a+c)-(b+d)$}\right)\right.\\
& \Rightarrow & a+c \equiv b+d \pmod n.
\end{array}
$$
\endclass{Wednesday, September 17}
\item
$$
\begin{array}{rc@{\quad}l}
\left.\begin{array}{r@{\ }l@{\quad}c@{\quad}r@{\ }l}
n & |(a-b) & \Rightarrow & n & |c(a-b)\\
n & |(c-d) & \Rightarrow & n & |b(c-d)
\end{array}
\right\}
& \Rightarrow & n\left|\left(\raisebox{0ex}[1.25\height]{$c(a-b)+b(c-d)$}\right)\right.\\
& \Rightarrow & n|(ca-cb+bc-bd)\\
& \Rightarrow & n|(ca-bd).\\
& \Rightarrow & ac \equiv bd \pmod n.
\end{array}
$$
\end{enumerate}
\end{proof}
\begin{definition}
\label{def:modular_ints_as_classes}
Let $n\in \Z$, $n\ge 1$. Given any $b\in \Z$ we define
$$
\cl b = \{a\in \Z \mid a\equiv b \pmod n\}.
$$
For example, we have
\begin{align*}
\cl {-2} & = \{a\in\Z \mid a \equiv -2 \pmod n\}\\
\cl 0 & = \{a\in\Z \mid a \equiv 0 \pmod n\}\\
\cl 3 & = \{a\in \Z \mid a\equiv 3 \pmod n\}
\end{align*}
In other words, $\cl b$ is the set of all integers that are congruent
to $b$ modulo $n$. We call this set the \define{congruence class of
$b$ modulo $n$}.
\end{definition}
\begin{comments}
There is another useful way to describe the set $\cl b$:
$$
\cl b = \{b+kn \st k\in \Z\}.
$$
This formula describes the same set since $a\equiv b \iff n|(a-b) \iff
a-b = kn \iff a=b+kn$.
\end{comments}
\begin{example}
Describe all the congruence classes of $\Z$ modulo $7$.
\begin{solution}
\begin{align*}
\cl 0 &= \{\ldots, -21, -14,-7,0,7,14,21,\ldots\}\\
\cl 1 &= \{\ldots, -20, -13,-6,1,8,15,22,\ldots\}\\
\cl 2 &= \{\ldots, -19, -12,-5,2,9,16,23,\ldots\}\\
\cl 3 &= \{\ldots, -18, -11,-4,3,10,17,24,\ldots\}\\
\cl 4 &= \{\ldots, -17, -10, -3,4,11,18,25,\ldots\}\\
\cl 5 &= \{\ldots, -16, -9, -2, 5,12,19,26,\ldots\}\\
\cl 6 &= \{\ldots, -15, -8, -1, 6, 13,20,27,\ldots\}
\end{align*}
Note that $\cl 7 = \{\dots, -14, -7, 0, 7, 14,\dots\} = \cl 0$, so we
don't bother putting $\cl 7$ on the list. Similarly, $\cl {-1} =
\l\dots, -15, -8, -1, 6, 13,\dots\} = \cl{6}$, so we don't bother
putting $\cl{-1}$ on the list. Similar comments apply to all the
other congruence classes.
\end{solution}
\end{example}
\begin{theorem}
Let $n\in \Z$, $n\ge 1$. For all $a,b\in \Z$ we have
$$
\cl a = \cl b
\quad\text{if and only if}\quad
a\equiv b \pmod n.
$$
\end{theorem}
\begin{proof}
\forwards. Let $\cl a = \cl b$. These are two sets that are equal, so
that every element of the first set is also an element of the second
set, and vice versa. By the reflexive property we have $a\equiv a$
and so $a\in \cl a$. Since $\cl a = \cl b$ we have $a\in \cl b$.
Therefore, by definition of $\cl b$, we have $a\equiv b$.
\backwards. Let $a\equiv b$. To prove that $\cl a = \cl b$ we need
to prove that the sets are equal. Let $c\in \cl a$. Then $c \equiv
a$. Since $a\equiv b$ the transitive property shows that $c\equiv
b$. Therefore $c\in \cl b$. This shows that $\cl a \subseteq \cl
b$. We can give the same argument for $c\in \cl b$, which proves $\cl
b \subseteq \cl a$. Thus, $\cl a = \cl b$.
\end{proof}
\begin{comments}
In general, when we intersect two sets, we expect to see some
nontrivial intersection
\begin{center}
\begin{tikzpicture}[scale=0.5]
\begin{scope}
% the following redraws the second circle, and fills it with light
% gray, but clips the result against the first circle.
\clip(135:2cm )circle (2cm);
\draw [fill=lightgray] (45:2cm) circle (2cm);
\end{scope}
\draw (135:2cm) circle (2cm) node {$A$}
(45:2cm) circle (2cm) node {$B$};
\end{tikzpicture}
\\
$A\cap B$
\end{center}
But in extreme cases the picture might look different: the overlap
might be everything, or nothing:
\begin{center}
\begin{tabular}{c@{\hspace*{1in}}c}
\begin{tikzpicture}[scale=0.5]
\draw (135:2cm) circle (2cm) node {$A=B$};
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.5]
\draw (0,0) circle (2cm) node {$A$};
\draw (4.5,0) circle (2cm) node {$B$};
\end{tikzpicture}
\\
$A=B=A\cap B$ & $A\cap B = \emptyset$
\end{tabular}
\end{center}
However, when the sets in question are congruence classes, only the
last two pictures are possible.
\end{comments}
\begin{example}
Let $n=13$. Explain as explicitly as possible how you know the
following are the same sets
\begin{align*}
\cl 7 & =\{\dots, -19, -6, 7, 20, 33,\dots\}\\
\cl {59} & = \{\dots, 33, 46, 59, 72, 85, \dots\}
\end{align*}
\begin{solution}
We can see explicitly that the sets have an element in common: $33$.
Now we use $33$ to connect elements from $\cl 7$ to elements of $\cl
{59}$, and vice versa.
If we look at an element like $-19\in \cl 7$, we see that $-19 \equiv
33$ because $33\in \cl 7$. Now since $33\in \cl {59}$ we see that
$-19\equiv 33 \equiv 59$, and so $-19\in \cl{59}$. Similarly, $85\in
\cl {59}$, $85\equiv 33 \equiv 7$ and so $85\in \cl 7$.
\end{solution}
\end{example}
\endclass{Monday, September 22}
\begin{cor}
\label{cor:distinct_classes_are_disjoint}
Let $a,b\in \Z$. Then
$$
\cl a = \cl b
\quad\text{or}\quad
\cl a\cap \cl b = \emptyset.
$$
In other words: two congruence classes are either the same class or
disjoint.
\end{cor}
\begin{proof}
If $\cl a \cap \cl b=\emptyset$ then we are done.
Otherwise, suppose $\cl a \cap \cl b \ne \emptyset$. Let $c\in \cl
a\cap \cl b$. Then $a\equiv c$ and $b\equiv c$. Let $d\in \cl a$.
Then $d\equiv a \equiv c \equiv b$ so $d\equiv b$ and $d\in \cl b$.
This shows that $\cl a\subseteq \cl b$. The same argument shows that
$\cl b \subseteq \cl a$ and so the sets are equal.
\end{proof}
\begin{cor}
Let $n\in \Z$, $n\ge 2$. The following hold:
\begin{enumerate}
\item If $a\in \Z$ and $r$ is the remainder of $a$ divided by $n$,
then $\cl a = \cl r$,
\item There are exactly $n$ distinct congruence classes:
$$
\cl 0, \cl 1, \dots, \cl {n-1}.
$$
We call $0$, $1$, $\dots$, $n-1$ the \define{canonical
representatives}.
\end{enumerate}
\end{cor}
\begin{definition}
% In a sense, this definition belongs in the next section, because
% we don't do anything with the set of all equivalence classes in
% this section. But, it follows well from the definition of
% canonical representatives.
The set of all equivalence classes modulo $n$ is denoted by $\Z_n$.
\end{definition}
\begin{comments}
Warning 1: the elements of $\Z_n$ are sets. Thus, it is correct to
write $\cl 5\in \Z_7$ but not $5\in \Z_7$.
Warning 2: Sometimes other notations are used: $\Z/(n)$ instead of
$\Z_n$.
\end{comments}
\section{Modular Arithmetic}
\begin{comments}
One of the topics of this section is how we can do arithmetic with
infinite sets. The next two examples should warm us up.
\end{comments}
\handoutpagebreak
\begin{example}
\label{example:even_odd_ring}
Fill in the following tables:
$$
\begin{array}{c|cc}
+ & \text{even} & \text{odd} \\\hline
\text{even} & & \\
\text{odd} & &
\end{array}
\quad
\begin{array}{c|cc}
\times & \text{even} & \text{odd} \\\hline
\text{even} & & \\
\text{odd} & &
\end{array}
$$
How do you prove these?
What does this have to do with arithmetic of infinite sets?
\begin{solution}
$$
\begin{array}{c|cc}
+ & \text{even} & \text{odd} \\\hline
\text{even} & \text{even} & \text{odd}\\
\text{odd} & \text{odd} & \text{even}
\end{array}
\quad
\begin{array}{c|cc}
\times & \text{even} & \text{odd}\\\hline
\text{even} & \text{even} & \text{even}\\
\text{odd} & \text{even} & \text{odd}
\end{array}
$$
These rules are (hopefully) really familiar and obvious. But wait!
Is everything so obvious? What about the proofs?
To prove one of these rules we go back to definitons and equations.
For instance, we need to know that an even number can be written as
$2x$ and an odd number as $2y+1$. So adding two even numbers looks
like $2x+2y=2z$ where $z=x+y$. Adding two odd numbers looks like
$(2x+1)+(2y+1) = 2(x+y)+2 = 2z$ where $z=x+y+1$. To prove that these
tables are correct one would check equations like this for each entry
in the tables.
What about infinite sets? There's an infinite number of even
integers, and an infinite number of odd integers, so these rules
describe how to add and multiply infinite sets!
\end{solution}
\end{example}
\handoutpagebreak
\begin{example}
\label{example_threeven_throd}
Greatly generalize the previous example as follows. ``Even'' and
``Odd'' are based on properties of the number $2$. Generalize these
properties to be based on the number $3$. Start by making up names
and meanings analagous to ``even'' and ``odd'', then make tables like
in the previous example. Explore the possibilities, and don't be
afraid to try the ``wrong'' thing.
\begin{solution}
Let's start by naming things: as soon as we have a name, then we can
objectify the name and manipulate it (in a good way).
Just to rhyme with the previous example, let's make up the following
names:
\begin{center}
\begin{tabular}{lp{3in}}
\threeven & = all numbers that are multiples of 3,\\
\throd & = all numbers that are not multiples of 3 (warning: this
definition will be changed in a couple of paragraphs).
\end{tabular}
\end{center}
Now, once we've made these names up, we would hope that they would
satisfy rules like the ones for even and odd:
$$
\begin{array}{c|cc}
+ & \text{\threeven} & \text{\throd} \\\hline
\text{\threeven} & \text{\threeven} & \text{\throd} \\
\text{\throd} & \text{\throd} & \text{\threeven}
\end{array}
\quad
\begin{array}{c|cc}
\times & \text{\threeven} & \text{\throd} \\\hline
\text{\threeven} & \text{\threeven} & \text{\threeven} \\
\text{\throd} & \text{\threeven} & \text{\throd}
\end{array}
\mbox{\Huge\bf ?}
$$
So let's check some of the above rules out.
\begin{align*}
\text{\threeven + \threeven} & \eq \text{\threeven} \\
3x + 3y & \eq 3z \\
z & = x+y \ \checkmark \text{correct} \\
\text{\threeven + \throd} & \eq \text{\throd} \\
3x+(3y+1) \text{ or }3x+(3y+2) & eq 3z + 1 \text{ or }3z+2 \\
z & = x+y \ \checkmark\text{correct} \\
\text{\throd + \throd} & \eq \text{\threeven} \\
(3x+1) + (3y+1) \text{ or }(3x+1)+(3y+2) \text{ or }(3x+2)+(3y+2) & \eq 3z+1 \text{ or }3z+2 \\
3x+3y+2 \text{ or } 3x+3y+3 \text{ or }3x+3y+4 & \eq 3z+1 \text{ or }3z+2 \\
3x+3y+3 & = 3z+1 \text{ or }3z+2 \text{ IMPOSSIBLE}
\end{align*}
What this means is that we have chosen the wrong sets of numbers to
add and multiply. The failed proof has hints of what we should have
done. The proof failed because of the combinatios of the $+1$ and the
$+2$ in our \throd numbers. In fact, there are two kinds of \throd
numbers, and they should each get a name and they should each define a
set:
\begin{center}
\begin{tabular}{lp{3.5in}}
\threeven & = all numbers that are multiples of 3,\\
\throd & = all numbers that are 1 bigger than a multiple of 3,\\
\throve & = all numbers that are 2 bigger than a multiple of 3.
\end{tabular}
\end{center}
Now we would try to fill in the following:
$$
\begin{array}{c|ccc}
+ & \text{\threeven} & \text{\throd} & \text{\throve} \\\hline
\text{\threeven} & &&\\
\text{\throd} & &&\\
\text{\throve} & &&
\end{array}
$$
and
$$
\begin{array}{c|ccc}
\times & \text{\threeven} & \text{\throd} & \text{\throve} \\\hline
\text{\threeven} & &&\\
\text{\throd} & &&\\
\text{\throve} & &&
\end{array}
$$
A little experimentation should provide the results we need. For
instance $2+5 = 7$ means \throve+\throve=\throd and $2\times 5 = 10$
means \throve$\times$\throve=\throd. The full results are shown below:
$$
\begin{array}{c|ccc}
+ & \text{\threeven} & \text{\throd} & \text{\throve} \\\hline
\text{\threeven} & \text{\threeven} & \text{\throd} & \text{\throve} \\
\text{\throd} & \text{\throd} & \text{\throve} & \text{\threeven} \\
\text{\throve} & \text{\throve} & \text{\threeven} & \text{\throd}
\end{array}
$$
and
$$
\begin{array}{c|ccc}
\times & \text{\threeven} & \text{\throd} & \text{\throve} \\\hline
\text{\threeven} & \text{\threeven} & \text{\threeven} & \text{\threeven} \\
\text{\throd} & \text{\threeven} & \text{\throd} & \text{\throve} \\
\text{\throve} & \text{\threeven} & \text{\throve} & \text{\throd}
\end{array}
$$
To prove these in general, we would work with the definitions. For
example, if $a$ is \throd and $b$ is \throve, then $a=3n+1$ and $b=3m+2$
for some $n,m\in \Z$. Then $a + b = 3(n+m+1)$, and is \threeven, and
$a \times b = (3n+1) (3m+2) = 9nm + 6n + 3m + 2 = 3(3nm + 2n + m) +
2$, which is \throve.
\end{solution}
\end{example}
\endclass{Wednesday, September 24}
\begin{comments}
The previous two examples show how easily we can add certain infinite
sets of numbers together. However, it is not always so easy, as the
next example shows.
\end{comments}
\handoutpagebreak
\begin{example}[Hungerford]
Define the following sets:
\begin{align*}
A & = \{\dots, -14, - 8, - 2, 0, 6, 12, 18,\dots\}\\
& = \{-2-6n\st n\in \N\} \cup \{0+6n\st n\in \N\}\\
B & = \{\dots, -11, -7, -3, 1, 6, 9, 13,\dots\}\\
& = \{4n+1\st n\in \Z\}\\
C & = \{\dots, -9, -5, -1, 3, 7, 11, 15,\dots\}\\
& = \{4n+3\st n \in \Z\}\\
D & = \{\dots, -16, -10, -4, 2, 8, 14, 20,\dots\}\\
& = \{6n+2 \st n\in \Z\}\\
E & = \{\dots, -18, -12, -6, 4, 10, 16, 22,\dots\}\\
& = \{-6-6n \st n\in \N\} \cup \{4+6n \st n\in \N\}
\end{align*}
\begin{enumerate}
\item Is every integer in one of these sets?
\item Do these sets have the property described in
Corollary~\ref{cor:distinct_classes_are_disjoint}: either they are
equal or they are disjoint?
\item Can you define an addition table for these sets based on adding
elements in the sets together?
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item Yes, every integer is in one of $A$, $B$, $C$, $D$, and $E$.
\item Yes, these sets are all disjoint from each other.
\item Let's try. What about $A+B$? If we pick $0\in A$ and $1\in B$,
we should have $0+1\in B$ and so $A+B=B$. On the other hand, if we
pick $-14\in A$ and $13\in B$ then $-14+13=-1\in C$. So which is
it? Should we define $A+B=B$ or $A+B=C$. We can't answer ``it
depends on which of $A$ and $B$ you use'' and we are only interested
in defining addition based on using elements. So no, it's
impossible. (Of course we can just make up what $A+B$ should be
without looking at all at the elements, and that's fine, but it's
not what the point of this example is about).
\end{enumerate}
\end{solution}
\end{example}
\handoutpagebreak
\begin{comments}
The next theorem shows that the problems we had in the previous
example do not arise when we are dealing with congruence classes.
\end{comments}
\begin{theorem}
Let $n\in \Z$, $n\ge 1$. Let $A$ and $C$ be equivalence classes in
$\Z_n$. Let $a,b\in A$ and $c,d\in C$. Then
$$
\cl{a+c} = \cl{b+d} \text{ and }\cl{ac} = \cl{bd}.
$$
In other words, it doesn't matter which elements we use in $A$ and $C$
to define addition and multiplicaiton.
\end{theorem}
\begin{proof}
Since $a,b\in A$ we have $a\equiv b \pmod n$ and similarly $c\equiv d
\pmod n$. Therefore $a+b\equiv c+d\pmod n$ and $ab\equiv cd\pmod n$
by Theorem~\ref{theorem:arithmetic_modulars_well_defined}.
\end{proof}
\begin{definition}
Let $n\in \Z$, $n\ge 1$. Let $\Z_n$ be the collection of all
equivalence classes of integers modulo $n$. The \define{canonical
representatives} of $\Z_n$ are as follows:
$$
\Z_n = \left\{\raisebox{0ex}[1.25\height]{$\cl 0, \cl1,\dots, \cl{n{-}1}$}\right\}.
$$
We define addition and multiplication in $\Z_n$ as follows:
$$
\cl a \oplus \cl c = \cl{a+c}
\text{ and }
\cl a \odot \cl c = \cl{ac}.
$$
\end{definition}
\handoutpagebreak
\begin{example}
Fill in the following addition and multiplation tables for $\Z_2$ and
$\Z_3$.
$$
\begin{array}{c|cc}
\oplus & \cl 0 & \cl 1 \\\hline
\cl 0 & & \\
\cl 1 & &
\end{array}
\qquad
\begin{array}{c|cc}
\odot & \cl 0 & \cl 1 \\\hline
\cl 0 & & \\
\cl 1 & &
\end{array}
$$
$$
\begin{array}{c|ccc}
\oplus
& \cl 0 & \cl 1 & \cl 2\\\hline
\cl 0 & & &\\
\cl 1 & &&\\
\cl 2 & &&
\end{array}
\qquad
\begin{array}{c|ccc}
\odot
& \cl 0 & \cl 1 & \cl 2\\\hline
\cl 0 & &&\\
\cl 1 & &&\\
\cl 2 & &&
\end{array}
$$
\begin{solution}
$$
\begin{array}{c|cc}
\oplus & \cl 0 & \cl 1 \\\hline
\cl 0 & \cl 0 & \cl 1 \\
\cl 1 & \cl 1 & \cl 0
\end{array}
\qquad
\begin{array}{c|cc}
\odot & \cl 0 & \cl 1 \\\hline
\cl 0 & \cl 0 & \cl 0 \\
\cl 1 & \cl 0 & \cl 1
\end{array}
$$
$$
\begin{array}{c|ccc}
\oplus
& \cl 0 & \cl1 & \cl 2\\\hline
\cl 0 & \cl 0 & \cl 1 & \cl 2\\
\cl 1 & \cl 1 & \cl 2 & \cl 0\\
\cl 2 & \cl 2 & \cl 0 & \cl 1
\end{array}
\qquad
\begin{array}{c|ccc}
\odot
& \cl 0 & \cl 1 & \cl 2\\\hline
\cl 0 & \cl 0 & \cl 0 & \cl 0\\
\cl 1 & \cl 0 & \cl 1 & \cl 2\\
\cl 2 & \cl 0 & \cl 2 & \cl 1
\end{array}
$$
\end{solution}
\end{example}
\handoutpagebreak
\begin{comments}
Now we compare the algebraic properties in $\Z$, as summarized in
Definition~\ref{definition:informal_integers}, with the algebraic
properties in $\Z_n$.
\end{comments}
\begin{theorem}
For all $\cl a$, $\cl b$, $\cl c$ in $\Z_n$ the following hold:
\begin{enumerate}
\renewcommand{\theenumi}{\textbf{Zn \arabic{enumi}}}
\item $\cl a\oplus (b\oplus c) = (\cl a\oplus b) \oplus c$,
\item $\cl a \oplus b = b \oplus \cl a$,
\item $\cl 0\oplus \cl a=\cl a\oplus \cl 0 = \cl a$,
\item $\cl a\oplus \cl{-a}=0$,
\item $\cl a\odot (\cl b\odot \cl c) = (\cl a\odot \cl b) \odot \cl c$,
\item $\cl a\odot \cl b = \cl b\odot \cl a$
\item $\cl a\odot \cl 1 = \cl a$
\item $\cl a\odot (\cl b \oplus \cl c) = (\cl a\odot \cl b) \oplus (\cl a\odot
\cl c)$
\end{enumerate}
\end{theorem}
\begin{comments}
The properties
\ref{Z_axiom_additive_order}--\ref{well_orderering_axiom} from
Definition~\ref{definition:informal_integers} do not apply to $\Z_n$,
because we have not defined what $\cl a < \cl b$ would mean. In fact,
there is no good way to define what $<$ should mean for $\Z_n$ so that
it satisfies property~\ref{Z_axiom_additive_order}.
\end{comments}
\begin{definition}
Let $\cl a \in \Z_n$ and let $k\in \N$. We define
\begin{align*}
k\cl a & = \cl a \oplus \dots \oplus \cl a \text{ (repeated $k$ times)}\\
\cl{a}^k & = \cl a \odot \dots \odot \cl a \text{ (repeated $k$ times)}
\end{align*}
\end{definition}
\begin{comments}
The previous definition carries some of the notation that we are
used to for $\Z$, $\R$, etc. over to $\Z_n$. In fact, we will in
general apply notation and conventions to $\Z_n$, when they make
sense. For example, we will assume that the order of operations is
applie in $\Z_n$ as in $\R$ so that $\cl a \oplus \cl b \odot \cl c$
means multiplication first, then addition.
\end{comments}
\begin{example}
Find all the solutions of $x^2\oplus \cl4\odot x = \cl 0$ in $\Z_7$.
(Try first just guessing and checking, but then try and be more
clever.)
\begin{solution}
\begin{multicols}{2}
\begin{align*}
x & \eq \cl 0\\
\cl 0^2\oplus \cl4\odot \cl 0 & = \cl 0 \oplus \cl 0 \\
& = \cl 0 \checkmark
\end{align*}
\begin{align*}
x & \eq \cl 1\\
\cl 1^2\oplus \cl4\odot \cl 1 & = \cl 1 \oplus \cl 4 \\
& = \cl 5 \text{ no}
\end{align*}
\begin{align*}
x & \eq \cl 2\\
\cl 2^2\oplus \cl4\odot \cl 2 & = \cl 4 \oplus \cl 8 \\
& = \cl {13}\\
& = \cl {6} \text{ no}
\end{align*}
\begin{align*}
x & \eq \cl 3\\
\cl 3^2\oplus \cl4\odot \cl 3 & = \cl 9 \oplus \cl {12} \\
& = \cl {21}\\
& = \cl {0} \checkmark
\end{align*}
\begin{align*}
x & \eq \cl 4\\
\cl 4^2\oplus \cl4\odot \cl 4 & = \cl {16} \oplus \cl {16} \\
& = \cl {32}\\
& = \cl {4} \text{ no}\
\end{align*}
\begin{align*}
x & \eq \cl 5\\
\cl 5^2\oplus \cl4\odot \cl 5 & = \cl {25} \oplus \cl {20} \\
& = \cl {45}\\
& = \cl {3} \text{ no}
\end{align*}
\begin{align*}
x & \eq \cl 6\\
\cl 6^2\oplus \cl4\odot \cl 6 & = \cl {36} \oplus \cl {24} \\
& = \cl {60}\\
& = \cl {4} \text{ no}
\end{align*}
\end{multicols}
We see that the only solutions are $x= \cl 0, \cl 3$. Now we find
them in a more clever way.
How would we solve this equation over $\R$, or over $\Z$? We would
factor. What makes factoring work? The first step is to apply the
distributive law, backwards. Since this law still holds for $\Z_n$,
we can apply it here too:
\begin{align}
\notag x^2\oplus \cl4\odot x & = \cl 0\\
\label{factored_equation_over_z_7}
x(x\oplus \cl 4) & = \cl 0\\
\label{factored_equation_over_z_7_x=0}
x & = \cl 0\\
\label{factored_equation_over_z_7_x+4=0}
x\oplus \cl 4 & = \cl 0\\
\notag x & = \cl{-4}\\
\notag & = \cl 3
\end{align}
WARNING: in this problem factoring gave the correct solutions, but
this will not always be the case. The problem isn't the step where we
factored, i.e.\ Equation~(\ref{factored_equation_over_z_7}). The
problem is that Equation~(\ref{factored_equation_over_z_7}) will
\emph{not} always imply
Equations~(\ref{factored_equation_over_z_7_x=0}) or
(\ref{factored_equation_over_z_7_x+4=0}). In any case, it's a good
idea to double check your answers, and we've done that above.
\end{solution}
\end{example}
\endclass{Friday, September 26}
\section{The structure of \texorpdfstring{$\Z_p$}{Zp} and \texorpdfstring{$\Z_n$}{Zn}}
\begin{definition}
We define new notation for the elements of $\Z_n$:
\begin{align*}
\text{old notation: } & \ \cl 0, \cl 1, \cl a,\text{ etc.}\\
\text{new notation: } & \ 0, 1, a \\
\end{align*}
and addition and multiplcation:
\begin{align*}
\text{old notation: } & 1\oplus 2, a\oplus b, 1\odot 2, a\odot b, \text{ etc.}\\
\text{new notation: } & 1+ 2, a+ b, 1\cdot 2 \text{ or }1\times 2, ab, \text{ etc.}\\
\end{align*}
and even for equivalence:
\begin{align*}
\text{old notation: } & 2+5\equiv 3 \pmod 4\\
\text{new notation: } & 2+5=3.
\end{align*}
The new notation has the advantage that there's a lot less to write,
and things look more similar to what we are used to with algebra in
$\Z$ and $\R$. It has the disadvantage that we have to remember that
we're not working over $\Z$ anymore, even though it looks like we are.
\end{definition}
\handoutpagebreak
\begin{example}
On the next page we have shown the addition and multiplication tables
for $\Z_{11}$ and $\Z_{12}$. Identify as many patterns and facts as
you can within each table, and also identify differences between the
$\Z_{11}$ and $\Z_{12}$ tables.
\begin{table}[p]
\vspace*{-0.5in}
\begin{gather*}
\Z_{11}
\quad
\left\{
\begin{array}{c}
\begin{array}{c|*{11}c}
+ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 0 \\
2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 0 & 1 \\
3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 0 & 1 & 2 \\
4 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 0 & 1 & 2 & 3 \\
5 & 5 & 6 & 7 & 8 & 9 & 10 & 0 & 1 & 2 & 3 & 4 \\
6 & 6 & 7 & 8 & 9 & 10 & 0 & 1 & 2 & 3 & 4 & 5 \\
7 & 7 & 8 & 9 & 10 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
8 & 8 & 9 & 10 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
9 & 9 & 10 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
10 & 10 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
\end{array}
\\
\\
\begin{array}{c|*{11}c}
\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
2 & 0 & 2 & 4 & 6 & 8 & 10 & 1 & 3 & 5 & 7 & 9 \\
3 & 0 & 3 & 6 & 9 & 1 & 4 & 7 & 10 & 2 & 5 & 8 \\
4 & 0 & 4 & 8 & 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 \\
5 & 0 & 5 & 10 & 4 & 9 & 3 & 8 & 2 & 7 & 1 & 6 \\
6 & 0 & 6 & 1 & 7 & 2 & 8 & 3 & 9 & 4 & 10 & 5 \\
7 & 0 & 7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\
8 & 0 & 8 & 5 & 2 & 10 & 7 & 4 & 1 & 9 & 6 & 3 \\
9 & 0 & 9 & 7 & 5 & 3 & 1 & 10 & 8 & 6 & 4 & 2 \\
10 & 0 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\
\end{array}
\end{array}
\right.
\\
\Z_{12}
\left\{\begin{array}{c}
\begin{array}{c|*{12}c}
+ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 \\
2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 \\
3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 \\
4 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 \\
5 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 \\
6 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 \\
7 & 7 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
8 & 8 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
9 & 9 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
10 & 10 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
11 & 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
\end{array}
\\
\\
{\addtolength{\arraycolsep}{1.1pt}
\begin{array}{c|*{12}c}
\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
2 & 0 & 2 & 4 & 6 & 8 & 10 & 0 & 2 & 4 & 6 & 8 & 10 \\
3 & 0 & 3 & 6 & 9 & 0 & 3 & 6 & 9 & 0 & 3 & 6 & 9 \\
4 & 0 & 4 & 8 & 0 & 4 & 8 & 0 & 4 & 8 & 0 & 4 & 8 \\
5 & 0 & 5 & 10 & 3 & 8 & 1 & 6 & 11 & 4 & 9 & 2 & 7 \\
6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 \\
7 & 0 & 7 & 2 & 9 & 4 & 11 & 6 & 1 & 8 & 3 & 10 & 5 \\
8 & 0 & 8 & 4 & 0 & 8 & 4 & 0 & 8 & 4 & 0 & 8 & 4 \\
9 & 0 & 9 & 6 & 3 & 0 & 9 & 6 & 3 & 0 & 9 & 6 & 3 \\
10 & 0 & 10 & 8 & 6 & 4 & 2 & 0 & 10 & 8 & 6 & 4 & 2 \\
11 & 0 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
}
\end{array}
\right.
\end{gather*}
\end{table}
\begin{solution}
For the addition tables we noticed these patterns:
\begin{itemize}
\item Each row equals the previous row shifted to the left one place.
\item The entries down the cross-diagonals (the diagonals with slope =
1) are constant.
\end{itemize}
For the addition and multiplication tables we noticed these patterns
\begin{itemize}
\item The entries in row $x$ are equal to the entries in column $x$.
\end{itemize}
For multiplication we noticed these:
\begin{itemize}
\item Conjecture: The number of distinct elements in row $x$ equals
$\frac{x}{\gcd(n,x)}$.
\item In $\Z_{11}$, the entries in each row/column have no repeats.
As a consquence, each entry appears exactly once in each row and
column.
\item In $\Z_{12}$, if $x$ is a nontrivial divisor of $12$, or a
multiple of one of these divisors, then row $x$ has repeats.
\item In $\Z_{12}$, if $x$ is not one of the above, then row $x$ has
no repeats.
\end{itemize}
After being prompted to think about when we have a row that equals
contains a $1$ or a nontrivial $0$, we came up with the following:
\begin{itemize}
\item In $\Z_{12}$, if $x$ shares a factor with $12$ then row $x$
contains a $0$.
\item In $\Z_{12}$, if $x$ is not one of the above, the row $x$
contains a $1$.
\item In $\Z_{11}$, every row contains a $1$.
\end{itemize}
\end{solution}
\end{example}
\handoutpagebreak
\begin{comments}
Some of the patterns and facts we observed in the previous example are
recorded in the two theorems of this section.
\end{comments}
\begin{definition}
Let $a\in \Z_n$. If $ax=1$ has a solution we call $a$ a
\define{unit}. If $ax=0$ has a solution with $a\ne 0$ and $x\ne 0$
we call $a$ a \define{zero divisor}
\end{definition}
\begin{theorem}[$\Z_p$ has only units, and no zero divisors]
\label{theorem:p_prime_equivalent_statements}
Let $p\in \Z$, $p>1$ (we do not assume that $p$ is prime). The
following statements are equivalent:
\begin{enumerate}
\item $p$ is prime,
\item for any $a\in \Z_p$\,, if $a\ne 0$ then the equation $ax=1$ has
a solution $x\in \Z_p$\,,
\item for all $a,b\in \Z_p$\,, if $ab=0$ then $a=0$ or $b=0$.
\end{enumerate}
\end{theorem}
\begin{example}
For each $a\in \Z_{11}$, identify a solution of $ax=1$.
\begin{solution}
$$
\begin{array}{cc}
a & x \\ \hline
1 & 1\\
2 & 6\\
3 & 4\\
4 & 3\\
5 & 9\\
6 & 2\\
7 & 8\\
8 & 7\\
9 & 5\\
10 & 10
\end{array}
$$
\end{solution}
\end{example}
\begin{proof}
``(1)$\Rightarrow$(2)'' Suppose $p$ is prime. Let $a\in \Z_p$ such
that $a\ne 0$.
\begin{align*}
\cl a & \ne \cl 0 \quad \text{ in }\Z_p& \text{given}\\
a & \not\equiv 0 \pmod p \text{ in }\Z & \text{restatement}\\
p & \notdiv a \text{ in }\Z & \text{restatement}\\
\gcd(a,p) & = 1 \text{ in }\Z& \text{$p$ is prime and previous line}\\
am + pn & = 1 \text{ in }\Z& \text{Previous line and Theorem~\ref{theorem:gcd_equals_Z_lin_comb}}\\
am & = 1-pn \text{ in }\Z& \text{previous line}\\
am & \equiv 1 \pmod p\text{ in }\Z\\
\cl{am} & = \cl{1} \text{ in }\Z_p\\
\cl a \cl m = & = \cl 1 \text{ in }\Z_p\\
x & = \cl m \text{ is a solution}
\end{align*}
\endclass{Monday, September 30}
``(2)$\Rightarrow$(3)'' Suppose that for any $a\in \Z_p$\,, $a\ne 0$,
the equation $ax=1$ has a solution $x\in \Z_p$. Let $ab=0$ in $\Z_p$.
If $a=0$ we are done. Otherwise, $a\ne 0$ and let $x=u$ be a solution
of $ax=1$.
\begin{align*}
ab & = 0 & \text{ given}\\
au & = 1 & \text{ for $a\ne 0$}\\
abu & = 0u & \text{mult 1st line by $u$}\\
(au)b & = 0 & \text{assoc. prop., $\times$ by $0$ prop.}\\
1b & = 0 & \text{2nd line}\\
b & = 0 & \text{mult by $1$ prop.}
\end{align*}
``(3)$\Rightarrow$(1)'' Suppose that for all $a,b\in \Z_p$\,, if
$ab=0$ then $a=0$ or $b=0$.
\begin{align*}
\forall \cl a, \cl b\in \Z_p, & \text{ if }\cl a \cl b = \cl 0 \text{ then }\cl a = \cl 0 \text{ or }\cl a = \cl 0\\
\forall a,b\in \Z, & \text{ if }ab\equiv 0 \pmod p \text{ then } a\equiv 0\pmod p \text{ or }b\equiv 0 \pmod p\\
\forall a,b\in \Z, & \text{ if }p|ab\text{ then }p|a \text{ or }p|b
\end{align*}
Then $p$ is prime by Theorem~\ref{theorem:Euclids_lemma}.
\end{proof}
\begin{theorem}[Classifying units and zero divisors in $\Z_n$]
Let $a\in \Z_n$\,, with $a\ne 0$.
\begin{enumerate}
\item $ax=1$ has a solution $x\in \Z_n$ if and only if $\gcd(a,n)=1$.
\item $ax=0$ has a nonzero solution $x\in \Z_n$ if and only if
$\gcd(a,n)\ne 1$.
\end{enumerate}
\end{theorem}
\begin{proof}
(1) \forwards direction. Suppose $ax=1$ has a solution in $\Z_n$.
\begin{align*}
au & = 1 \text{ in }\Z_n & \text{given}\\
\cl a \cl u & = \cl 1 \text{ in }\Z_n & \text{restatement}\\
a u & \equiv 1 \pmod n \text{ in }\Z & \text{restatement}\\
a u & = 1+ nk \text{ in }\Z & \text{definition of $\equiv$}\\
a u -n k & = 1 & \text{restatement}\\
\gcd(a,n) & = 1 & \text{Theorem~\ref{theorem:gcd_equals_Z_lin_comb}}
\end{align*}
(1)\backwards direction. Suppose $\gcd(a,n)=1$. Repeat the second half of the
proof of Theorem~\ref{theorem:p_prime_equivalent_statements} where we
showed ``(1)$\Rightarrow$(2)''.
\begin{align*}
ar + ns & = 1 \text{ in }\Z& \text{Theorem~\ref{theorem:gcd_equals_Z_lin_comb}}\\
ar & = 1-ns \text{ in }\Z& \text{previous line}\\
ar & \equiv 1 \pmod n\text{ in }\Z\\
\cl{ar} & = \cl{1} \text{ in }\Z_n\\
\cl a \cl r = & = \cl 1 \text{ in }\Z_n\\
x & = \cl r \text{ is a solution}
\end{align*}
\end{proof}
\begin{scholium}
If $\gcd(a,n)=1$, then the solution of $ax=1$ in $\Z_n$ is given by
$x=r$ where $ar+ns=1$ in $\Z$.
\end{scholium}
\begin{example}
Identify the units and zero divisors in $\Z_{12}$. In each case
identify both $a$ and $x$.
\begin{solution}
$$
\begin{array}{*4c}
\text{Units} & \text{Zero Divisors} & ax=1 & ax=0\\
1,5,7,11 & 2,3,4,6,8,9,10
&
\begin{array}[t]{cc}
a & x\\ \hline
1 & 1\\
5 & 5\\
7 & 7\\
11 & 11\\
\end{array}
&
\begin{array}[t]{cc}
a & x\\ \hline
2 & 6\\
3 & 4\\
4 & 3\\
6 & 2\\
8 & 3\\
9 & 4\\
10 & 6\\
\end{array}
\end{array}
$$
\end{solution}
\end{example}
\end{document}
