\documentstyle{article}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 609/597: Cryptography \hrulefill }
\markboth{\headlineaux}{\headlineaux}

\newcommand{\set}[2]{\bigl\{\, #1 \,\big|\, #2 \,\bigr\}}
\newcommand{\implies}{\Rightarrow}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newenvironment{proof}{\noindent{\sc Proof:~}}{\hfill$\Box$\par\medskip}
\newcommand{\divides}{\,|\,}
\newcommand{\ZZ}{{\bf Z}}


\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section{Basic Definitions}

\begin{definition} The {\em translate of $m\ZZ$ by $k$} is the
set of all integers that can be written as $k$ plus a multiple
of $m$:
\[ k + m\ZZ = \set{ k + im }{ i\in \ZZ }.\]
\end{definition}

Visualizing this subset of the integers, it is not hard
to see that two translates either coincide completely or
have no integer in common.
Also, that any integer is in some translate. Hence,
the collection of distinct translates partitions the
integers and therefore gives rise to an equivalence
relation.

To prove these statements formally
we will make use of the properties of divisibility to
give an alternative characterization of translates
according to a divisibility criteria.

\begin{definition}
For integer $a,b\in\ZZ$, {\em $a$ divides $b$}, written
$a\divides b$, if and only if there exists an integer $k\in \ZZ$
such that $ak=b$.
\end{definition}

The familiar property of divisibility that we shall use,
but not prove is the following:

\begin{theorem}
Suppose $a, b, c\in\ZZ$ are integers and $c$ divides $a$ and $b$.
Then $c$ divides all linear combinations of $a$
and $b$, that is, for all $x,y\in\ZZ$, $c\divides (xa+yb)$.
\end{theorem}

We now give an alternative definition for translates.

\begin{theorem} Two integers are in the same translate of
$m\ZZ$ if and only if their difference is divisible by $m$.
That is, for all $a,b\in\ZZ$, $a,b\in (k+m\ZZ)$ for some
integer $k$ if and only if $m\divides (a-b)$.
\end{theorem}

\begin{proof}
Suppose $a,b\in(k+m\ZZ)$. Then there are integers 
$i_a,i_b$ such that,
\[ a = k + i_a m,\;\; b = k + i_b m.\]
Subtracting, $a-b=(i_a-i_b)m,$ which is divisible by $m$.

Suppose now that we have $a,b\in\ZZ$ where $m\divides (a-b)$.
Then there is an $i$ such that $mi=a-b$, so, $a\in b+m\ZZ$.
Obviously, $b\in b+m\ZZ$, so $a$ and $b$ are in the same
translate.
\end{proof}

\begin{theorem} Given an $m\in\ZZ$, 
two translates $k_1+m\ZZ$ and $k_2+m\ZZ$ are either disjoint
or identical, depending on whether $m$ divides $k_1-k_2$ or not,
and the set of distinct translates covers all of $\ZZ$.
\end{theorem}

\begin{proof}
Suppose two translates $k_1+m\ZZ$ and $k_2+m\ZZ$ are not disjoint.
Let $z$ be an integer in both. So,
\[ m\divides (z-k_1),\;\; m\divides(k_2-z),\]
and adding these two, 
\[ z-k_1+(k_2-z) = k_2-k_1 \implies m\divides(k_2-k_1).\]
So, if the translate are not disjoint, $k_1$ and $k_2$ are 
in the intersection.
Take an arbitrary $z\in k_1+m\ZZ$. It is in the same
translate as $k_2$. So $m\divides (z-k_2)$, therefore
$z\in k_2+m\ZZ$. Likewise, any $z\in k_2+m\ZZ$ is in
$k_1+m\ZZ$. This shows that the two translates are identical.

Conversely, if $m\divides(k_1-k_2)$, then $k_1\in k_2 +m\ZZ$,
and the translates are not disjoint.

Every $z\in\ZZ$ is in some translate, namely $z\in z+m\ZZ$.
\end{proof}

\begin{corollary}
If $k'\in k+m\ZZ$, then $k'+m\ZZ=k+m\ZZ$.
\end{corollary}

\begin{definition}
We say that two integer $a,b\in\ZZ$ are {\em congruent modulo $m$}
if they are in the same translate of $m\ZZ$. This is
written $a=b\pmod{m}$.
\end{definition}

Each translate is an {\em equivalence class}, it is the set of
all integers which share equality under congruence modulo $m$.
Typically, each equivalence class takes its name from the
smallest non-negative integer in the class. 

\begin{theorem}
The set $\{\,0, 1, \ldots, m-1\,\}$ runs through all equivalence
classes modulo $m$. That is, given any $z\in\ZZ$, there is
exactly one $r$ between $0$ and $m-1$ for which $z=r\pmod{m}$.
\end{theorem}
\begin{proof}
Consider $z+m\ZZ$. This translate must contain one and
only one integer $r$ in the range $0\le r<m$. For if $r'$ were the 
smallest non-negative integer in $z+m\ZZ$ and $r'\ge m$, then
$r'-m$ would be non-negative and smaller than $r'$. And
if there were two integer $0\le r\le r'<m$ then $m\divides (r'-r)$
however $0\le r'- r<m$, so $r'-r$ must be zero.
\end{proof}

\section{Arithmetic modulo $m$}

\begin{theorem} Given an $m\in\ZZ$ and two translates
$a+m\ZZ$ and $b+m\ZZ$, for any two $a_1$ and $a_2$
in $a+m\ZZ$ and $b_1$ and $b_2$ in $b+m\ZZ$, 
\[ (a_1+b_1)+m\ZZ = (a_2+b_2) + m\ZZ,\]
and
\[ (a_1b_1)+m\ZZ=(a_2b_2)+m\ZZ.\]
\end{theorem}
\begin{proof}
Write $a_1=a_2+i_a m$ and $b_1=b_2+i_bm$. Then,
\begin{eqnarray*}
  a_1+b_1 &=& a_2 + b_2 + (i_a+i_b)m \\
          &=& a_2 + b_2 + i'm,\\
\end{eqnarray*}
Hence $(a_1+b_1)\in(a_2 + b_2)+m\ZZ,$ and the first equality holds.
Likewise,
\begin{eqnarray*}
  a_1b_1 &=& a_2 b_2 + (i_ba_2+i_ab_2+i_ai_bm)m \\
   &=& a_2 b_2 + i''m,\\
\end{eqnarray*}
so the second equality holds.
\end{proof}

Hence a well-defined arithmetic can be defined for translates
based on the arithmetic of integers.

\begin{definition}
We define the sum of translates to be,
\[ \bigl(a+m\ZZ\bigr) + \bigl(b+m\ZZ\bigr) = 
    (a+b)+ m\ZZ,\]
and their product to be,
\[ \bigl(a+m\ZZ\bigr) \bigl(b+m\ZZ\bigr) =
(ab)+m\ZZ.\]
By the previous theorem, this definition depends only on the
translates, not the $a$ and $b$ used to describe the translate.
\end{definition}

Translated into the language of congruences, we have the theorem,
\begin{corollary} If 
\[ a_1=a_2 \mbox{ and }b_1=b_2\pmod{m},\]
then
\[a_1+b_1=a_2+b_2 \mbox{ and } a_1b_1=a_2b_2\pmod{m}.\]
\end{corollary}

Since the defined arithmetic is based on that of
the integers, it inherits many properties from the integers. 
Addition modulo $m$
is an associative and commutative operation,
and for each translate $T$ there is a unique translate $-T$,
its {\em additive inverse}, for which $T+(-T)=0+m\ZZ$.
Multiplication modulo $m$ is also an associative
and commutative operation which distributes
over addition, that is, for three translates $T_1, T_2$ and $T_3$,
\[ T_1(T_2+T_3)= T_1T_2 + T_1T_3.\]

Having defined addition and multiplication modulo $m$, we next look
at division. For the integers, one can only divide by $1$ or $-1$.
As for the rest, {\em fractions} are invented, where the inverse
of $i$ is $1/i$ for $i\neq 0$, being careful to discover and make
all identifications, such as that $2/4$ is the same as $1/2$.
For the integers modulo $m$ the situation is different. If may
happen that just taking the integer $x$ modulo $m$ creates a
{\em multiplicative inverse} for that number,
that is, an $x^{-1}$ such that $x^{-1}x=xx^{-1}=1$ modulo
$m$. On the other hand, it may cause $x$ to become a
{\em divisors of zero}, that is, $x$ is non-zero modulo $m$,
however there is another number $y$, non-zero modulo $y$, such that
$xy=0$ modulo $m$.
If it was the case that $x^{-1}$ existed, we would have,
\[ y = 1y = (x^{-1}x)y = x^{-1}(xy) = x^{-1}0=0,\]
so no inverse to $x$ could exist or be created without forcing
$y$ to become $0$.

In general, let us consider the solution for $x$ to the
equation,
\[ ax=b\pmod{m}.\]
This means that $ax$ is in $b+m\ZZ$, that is, that there exists
an $i\in\ZZ$ such that,
\[ ax=b+mi.\]
To this end, we look at all linear combinations of $a$ and $m$.
\newcommand{\lin}[2]{\langle\,#1,#2\,\rangle}
\begin{definition} The set of linear combinations of
two integers $s$ and $t$ is denoted $\lin s t,$
\[ \lin s t  = \set{is+jt}{i,j\in\ZZ}.\]
\end{definition}
The existence of a solution $x$ of the above equation is
equivalent to whether or not $b\in\lin a m.$
There are some obvious and not so obvious facts about
$\lin a b.$
\begin{theorem}
For all $a,b\in\ZZ$ integers,
\begin{enumerate}
\item $\lin a b = \lin b a.$
\item $\lin {-a} b = \lin a b.$
\item $\lin a b = \lin {a-b} b.$
\item $\lin a b = \lin b r$ where $a\ge b> 0$ and $r$ is the remainder
of $a\div b$.
\end{enumerate}
\end{theorem}
\begin{proof} The first two facts are the obvious ones.
For the third, the computation,
\[ ia+jb = ia-ib+(i+j)b = i(a-b)+(i+j)b,\]
implies that anything in $\lin a b$ is in $\lin {a-b} b$, and
vice a versa.
For $a\ge b>0$, write $a=qb+r$ and apply Fact Three $q$ times,
\[ \lin a b = \lin {a-qb} b = \lin r b = \lin b r.\]
\end{proof}

\begin{definition} Let $a,b\in\ZZ$ be integers. The set of
{\em common divisors} of $a$ and $b$ is,
\[ \set{c\in\ZZ}{c\divides a\mbox{ and }c\divides b}.\]
Except in the case when $a$ and $b$ are both zero,
the largest element in the set of common divisors of $a$ and
$b$ is called the {\em greatest common divisor of $a$ and $b$.}
The greatest common divisor of zero and zero
is defined to be zero.
\end{definition}

\begin{theorem} The set of all linear combinations of two
integer $a$ and $b$ is the same as the set of all multiples
of the greatest common divisor $d$ of $a$ and $b$,
\[ \lin a b = d\ZZ.\]
\end{theorem}
\begin{proof}
Starting from $\lin a b$, use the above properties
to arrange things
so that $\lin a b = \lin {s_0}{s_1}$ and $s_0\ge s_1 \ge 0$.
Let $s_2$ be the remainder of $s_0$ divided by $s_1$, in the
case that $s_1$ is not zero, and repeat this process, getting
a sequence of $s_i$ such that $\lin {s_{i-2}} {s_{i-1}}
= \lin {s_{i-1}} {s_i}$ and $s_i$ is the remainder of
$s_{i-2}$ divided by $s_{i-1}$. This process must terminate
when $s_j=0$, in which case we have,
\[ \lin a b = \lin {s_{j-1}} 0 = \set{s_{j-1}i}{i\in\ZZ}.\]
Since both $a$ and $b$ are in $s_{j-1}\ZZ$, they are multiples of
$s_{j-1}$, so $s_{j-1}$ is a common divisor of $a$ and $b$.
If $c$ was any other common divisor of $a$ and $b$, it would
divide $xa+by$ for all $x,y\in \ZZ$, hence $c$ divides
anything in $\lin a b$. But $s_{j-1}\in\lin a b$, so $c\divides
s_{j-1}$. Thus $s_{j-1}$ is the greatest common divisor of $a$ and $b$.
\end{proof}

\begin{theorem}
In the previous theorem, let $A=\max (\,|\,a\,|,|\,b\,|\,).$ Then
the length of the sequence of remainders $s_0, \ldots, s_j$ is
bound by,
\[ j \le 2 \log_2 A. \]
\end{theorem}
\begin{proof}
Each two steps the larger value is lessened by at least half.
That is,
\[ \max( s_{i+3}, s_{i+2} ) \le \max (s_i, s_{i+1}) /2.\]
This is already true after one step if $s_{i+1} \le s_i/2$. 
So suppose $s_i/2 < s_{i+1}\le s_i$. Then in the first
step, $s_{i+2}$ is calculated,
\[ s_{i+2} = s_i - s_{i+1} < s_i/2,\]
and and in the second step $s_{i+3}$ is
calculated $s_{i+3}\le s_{i+2}$.

Hence the number of pairs of steps cannot be longer than
required to bring $A$ to the minimum
value attainable,
\[ 1 \le A/(2^{j/2}).\]
Now take the $\log$ of both sides and solve for $j$.
\end{proof}

Therefore we also have an efficient method for calculating
the greatest common divisor of $a$ and $b$. Coming back to
the original problem, we now have an efficient method to
determine if there exists an $x$ such that,
\[ ax = b \pmod{m}.\]
We calculate the $d$ such that $\lin a m = d\ZZ$, and if
$b\in d\ZZ$, that is if $d\divides b$, then there is a 
solution. Else there is no solution.

The algorithm for calculating $d$ can be modified to also
give the $i$ and $j$ such that $ai+jm = d$. In the case
that $d$ divides $b$, we multiply through by the $k$ such
that $dk=b$,
\[ a(ki) + kjm = kd = b,\]
and so $b\in a(ki)+ m\ZZ$, 
\[ a(ki) = b \pmod{m}.\]

We have not yet discussed the uniqueness of the solution, if
it exists.
If the greatest common divisor of $a$
and $m$ is $1$, then the equation $ax=b$ has a solution for
every possible $b$.
Therefore, there are only enough elements to go around for one
$x$ to be a solution for each specific $b$.
On the other hand, if the greatest common divisor is $d>1$, then
only $m/d$ such equations have solutions, meanwhile for every
$x$ the multiplication $ax$ must evaluate to something.

Suppose we have a solution $ax'=b$ (modulo $m$) where 
$\lin a m = d\ZZ$. Then $x''=x'+i(m/d)$ are also solutions
for $i=1,\ldots, d-1$, because,
\[ ax'' = a(x'+i(m/d)) = ax' + ai(m/d) = ax' = b \pmod{m},\]
remarking that $m\divides ai(m/d)$.
Furthermore, $i(m/d)$ are all unique modulo $m$, for $i=
0,\ldots, d-1$, so there are $d$ solutions in this case.

\begin{theorem} In the integers modulo $m$, let $a$ and $b$
be integers, and $d$ the greatest common divisor of $a$ and $m$.
Then the equation,
\[ ax = b \pmod{m}\]
has $d$ solutions if $d\divides b$.
Else there are no solutions.
\end{theorem}

\end{document}

