\hyperdef{modular}{arithmetic}{\section{Modular Arithmetic}}
\label{sec:modular-arithmeric}

% Congruence is a weak form of equality.

On page 1 of his masterpiece on number theory, {\em Disquisitiones
Arithmeticae}, Gauss introduced the notion of ``congruence''.  Now,
Gauss is another guy who managed to cough up a half-decent idea every
now and then, so let's take a look at this one.  Gauss said that
\term{$a$ is congruent to $b$ modulo $n$} iff $n \divides (a - b)$.  This
is denoted $a \equiv b \pmod{n}$.  For example:
%
\[
29 \equiv 15 \pmod{7}  \quad\text{ because }  7 \divides (29 - 15).
\]

There is a close connection between congruences and remainders:
\begin{lemma}[Congruences and Remainders]
\label{lem:conrem}
\[
a \equiv b \pmod{n} \qiff \rem{a}{n} = \rem{b}{n}.
\]
\end{lemma}

\begin{proof}
By the Division Theorem, there exist unique pairs of integers $q_1, r_1$
and $q_2, r_2$ such that:
%
\begin{align*}
a & = q_1 n + r_1 & \text{where $0 \leq r_1 < n$}, \\
b & = q_2 n + r_2 & \text{where $0 \leq r_2 < n$}.
\end{align*}
%
In these terms, $\rem{a}{n} = r_1$ and $\rem{b}{n} = r_2$.
Subtracting the second equation from the first gives:
%
\begin{align*}
a - b & = (q_1 - q_2) n + (r_1 - r_2)
  & \text{where $-n < r_1 - r_2 < n$}.
\end{align*}
%
Now $a \equiv b \pmod{n}$ if and only if $n$ divides the left side.
This is true if and only if $n$ divides the right side, which holds if
and only if $r_1 - r_2$ is a multiple of $n$.  Given the bounds on
$r_1 - r_2$, this happens precisely when $r_1 = r_2$, which is
equivalent to $\rem{a}{n} = \rem{b}{n}$.
\end{proof}

So we can also see that
\[
29 \equiv 15 \pmod{7} \quad\text{ because } \rem{29}{7} = 1 = \rem{15}{7}.
\]
This formulation explains why the congruence relation has properties like
an equality relation.  Notice that even though (mod 7) appears over on the
right side the $\equiv$ symbol, it is in no sense more strongly associated
with the 15 than the 29.  It would really be clearer to write $29
\equiv_{\mod 7} 15$ for example, but the notation with the modulus at the
end is firmly entrenched and we'll stick to it.

We'll make frequent use of the following immediate Corollary of
Lemma~\ref{lem:conrem}:
\begin{corollary}\label{aran}
\[
a \equiv \rem{a}{n} \pmod{n}
\]
\end{corollary}

Still another way to think about congruence modulo $n$ is that it
\emph{defines a partition of the integers into $n$ sets so that congruent
numbers are all in the same set}.  For example, suppose that we're working
modulo 3.  Then we can partition the integers into 3 sets as follows:
%
\[
\begin{array}{cccccccccc}
\{ & \dots, & -6, & -3, & 0, & 3, & 6, & 9, & \dots & \} \\
\{ & \dots, & -5, & -2, & 1, & 4, & 7, & 10, & \dots & \} \\
\{ & \dots, & -4, & -1, & 2, & 5, & 8, & 11, & \dots & \}
\end{array}
\]
according to whether their remainders on division by 3 are 0, 1, or 2.
The upshot is that when arithmetic is done modulo $n$ there are really
only $n$ different kinds of numbers to worry about, because there are only
$n$ possible remainders.  In this sense, modular arithmetic is a
simplification of ordinary arithmetic and thus is a good reasoning tool.

There are many useful facts about congruences, some of which are listed in
the lemma below.  The overall theme is that \textit{congruences work a lot
like equations}, though there are a couple of exceptions.

\begin{lemma}[Facts About Congruences]  The following  hold for 
$n \geq 1$:
%
\begin{enumerate}
\item $a \equiv a \pmod{n}$
\item $a \equiv b \pmod{n}$ implies $b \equiv a \pmod{n}$
\item $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$ implies $a \equiv c \pmod{n}$
\item $a \equiv b \pmod{n}$ implies $a + c \equiv b + c \pmod{n}$
\item $a \equiv b \pmod{n}$ implies $a c \equiv b c \pmod{n}$
\item $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ imply $a + c
\equiv b + d \pmod{n}$
\item $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ imply $a c
\equiv b d \pmod{n}$
\end{enumerate}
\end{lemma}

\begin{proof}
Parts 1.--3.\ follow immediately from Lemma~\ref{lem:conrem}.  Part 4.\
follows immediately from the definition that $a \equiv b \pmod{n}$ iff $n
\divides (a-b)$.  Likewise, part 5.\ follows because if $n \divides (a-b)$
then it divides $(a-b)c = ac - bc$.  To prove part 6., assume
\begin{equation}\label{ab}
a \equiv b \pmod{n}
\end{equation}
and
\begin{equation}\label{cd}
c \equiv d \pmod{n}.
\end{equation}
Then
\begin{align*}
a + c & \equiv b + c \pmod{n} & \text{(by part 4.\ and~\eqref{ab}}),\\
c + b & \equiv d + b \pmod{n} & \text{(by part 4.\ and~\eqref{cd}), so}\\
b + c & \equiv b + d \pmod{n} & \text{and therefore}\\
a + c & \equiv b + d \pmod{n} & \text{(by part 3.)}
\end{align*}
Part 7.\ has a similar proof.
\end{proof}

\iffalse

There is a close connection between modular arithmetic and the
remainder operation, which we looked at last time.  To clarify this
link, let's reconsider the partition of the integers defined by
congruence modulo 3:
%
\[
\begin{array}{cccccccccc}
\{ & \dots, & -6, & -3, & 0, & 3, & 6, & 9, & \dots & \} \\
\{ & \dots, & -5, & -2, & 1, & 4, & 7, & 10, & \dots & \} \\
\{ & \dots, & -4, & -1, & 2, & 5, & 8, & 11, & \dots & \}
\end{array}
\]
%
Notice that two numbers are in the same set if and only if they leave
the same remainder when divided by 3.  The numbers in the first set
all leave a remainder of 0 when divided by 3, the numbers in the
second set leave a remainder of 1, and the numbers in the third leave
a remainder of 2.  Furthermore, notice that each number is in the same
set as its own remainder.  For example, 11 and $\rem{11}{3} = 2$ are
both in the same set.  Let's bundle all this happy goodness into a
lemma.
\fi

\TBA{put in 'example' environment}

\subsection{Turing's Code (Version 2.0)}

In 1940 France had fallen before Hitler's army, and Britain alone stood
against the Nazis in western Europe.  British resistance depended on a
steady flow of supplies brought across the north Atlantic from the United
States by convoys of ships.  These convoys were engaged in a cat-and-mouse
game with German ``U-boats'' ---submarines ---which prowled the Atlantic,
trying to sink supply ships and starve Britain into submission.  The
outcome of this struggle pivoted on a balance of information: could the
Germans locate convoys better than the Allies could locate U-boats or vice
versa?

Germany lost.

But a critical reason behind Germany's loss was made public only in
1974: the British had broken Germany's naval code, Enigma.  Through
much of the war, the Allies were able to route convoys around German
submarines by listening into German communications.  The British
government didn't explain \textit{how} Enigma was broken until 1996.
When the analysis was finally released (by the US), the author was
none other than Alan Turing.  In 1939 he had joined the secret British
codebreaking effort at Bletchley Park.  There, he played a central
role in cracking the German's Enigma code and thus in preventing
Britain from falling into Hitler's hands.

Governments are always tight-lipped about cryptography, but the
half-century of official silence about Turing's role in breaking
Enigma and saving Britain may be related to some disturbing events
after the war.

Let's consider an alternative interpretation of Turing's code.
Perhaps we had the basic idea right (multiply the message by the key),
but erred in using \textit{conventional} arithmetic instead of
\textit{modular} arithmetic.  Maybe this is what Turing meant:
%
\begin{description}

\item[Beforehand] The sender and receiver agree on a large prime $p$,
which may be made public.  (This will be the modulus for all our
arithmetic.)  They also agree on a secret key $k \in \set{1, 2,
\dots, p-1}$.

\item[Encryption] The message $m$ can be any integer in the set
$\set{0, 1, 2, \dots, p-1}$; in particular, the message is no longer
required to be a prime.  The sender encrypts the message $m$ to
produce $m^*$ by computing:
%
\begin{equation}
m^* = \rem{mk}{p} \label{eq:turing-code}
\end{equation}

\item[Decryption] (Uh-oh.)

\end{description}

The decryption step is a problem.  We might hope to decrypt in the
same way as before: by dividing the encrypted message $m^*$ by the key
$k$.  The difficulty is that $m^*$ is the \textit{remainder} when $mk$
is divided by $p$.  So dividing $m^*$ by $k$ might not even give us an
integer!

This decoding difficulty can be overcome with a better understanding
of arithmetic modulo a prime.

\endinput