%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{makeidx}
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="31">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="The Integers Modulo m">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Thu Feb 13 16:57:08 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=MathHelp.cst}
%TCIDATA{<LINK REL="author" HREF="DM0-1.tex">}
%TCIDATA{<LINK REL="first" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="contents" HREF="DM0-0.tex">}
%TCIDATA{<LINK REL="copyright" HREF="DM0-2.tex">}
%TCIDATA{<LINK REL="end" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="index" HREF="DMIndex.tex">}
%TCIDATA{<LINK REL="next" HREF="DM12-3.tex">}
%TCIDATA{<LINK REL="parent" HREF="DM12.tex">}
%TCIDATA{<LINK REL="previous" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="top" HREF="DM0-0.tex">}

\input{tcilatex}
\begin{document}


\section{\label{Integers modulo m}The \label{Congruence}Integers \label%
{mod function}Modulo m}

Two integers $a$ and $b$ are 
\index{Congruence@Congruence}\textsl{congruent modulo} $m$ if and only if $%
a-b$ is a multiple of \thinspace $m$, in which case we write $a\equiv
b\,\left( 
\limfunc{mod}m\right) $. 
\index{Modulo@Modulo}\label{Modulo}Thus, $15\equiv 33\,\left( 
\limfunc{mod}9\right) $, because $15-33=\,-18$ is a multiple of $9$. 
\index{Residue@Residue}\label{Residue}Given integers $a$ and $m$, the 
\index{Mod@mod}\textsl{mod function} is given by $a%
\limfunc{mod}m=b$ if and only if $a\equiv b\,\left( \limfunc{mod}m\right) $
and $0\leq b\leq m-1$; hence, $a\limfunc{mod}m$ is the smallest \textsl{%
nonnegative residue} of $a$ modulo $m$.

The underlying computer algebra system does not understand the congruence
notation $a\equiv b\left( \limfunc{mod}m\right) $, but it does understand
the function notation $a\limfunc{mod}m$. This section shows how to translate
problems in algebra and number theory into language that \textsl{Scientific
Notebook} can handle.

Note that $\limfunc{mod}$ is a function of two variables, with the function
written between the two variables. This usage is similar to the common usage
of $+$, which is also a function of two variables with the function values
expressed as $a+b$, rather than the usual functional notation $+(a,b)$.

Traditionally the congruence notation $a\equiv b\,\left( \limfunc{mod}%
m\right) $ is written with the $\func{mod}m$ enclosed inside parentheses
since the $\func{mod}m$ clarifies the expression $a\equiv b$. In this
context, the expression $b\,\left( \limfunc{mod}m\right) $ never appears
without the preceding $a\equiv $. On the other hand, the $\func{mod}$
function is usually written in the form $a\func{mod}m$ without
parentheses.\medskip

\begin{quote}
$\blacktriangleright $ To evaluate the mod function
\end{quote}

\begin{enumerate}
\item[1.]  Leave the insertion point in the expression $a\limfunc{mod}b.$

\item[2.]  Choose \textsf{Evaluate.\medskip }
\end{enumerate}

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$23\limfunc{mod}14=9\medskip $
\end{quotation}

\ 

If $a$ is positive, you can also find the smallest nonnegative residue of $a$
modulo $m$ by applying \textsf{Expand} to the quotient $\frac{a}{m}$.

\begin{quote}
$\blacktriangleright $ \textsf{Expand}
\end{quote}

\begin{quotation}
$\dfrac{23}{14}=1\dfrac{9}{14}$
\end{quotation}

\ 

Since $1\frac{9}{14}=1+\frac{9}{14}$, multiplication of $\frac{23}{14}=1+%
\frac{9}{14}$ by $14$ shows that $23\limfunc{mod}14=9$.

In terms of the \hyperref{floor}{}{}{DM2-4.tex#Floor} function $\left\lfloor
x\right\rfloor $, the mod function is given by $a\func{mod}m=a-\left\lfloor 
\frac{a}{m}\right\rfloor m$ .\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$23-\left\lfloor \frac{23}{14}\right\rfloor 14=9$
\end{quotation}

\strut

\subsection{\ \label{Multiplication table mod m}Multiplication Tables Modulo
m}

You can make tables that display the products modulo $m$ of pairs of
integers from the set $\left\{ 0,1,2,\ldots ,m-1\right\} $.\medskip

\begin{quote}
$\blacktriangleright $ To get a multiplication 
\index{Multiplication table@Multiplication table}table modulo $m$ with $m=6$
\end{quote}

\begin{enumerate}
\item[1.]  Define the function $g(i,j)=(i-1)(j-1)$.

\item[2.]  From the \textsf{Matrices} submenu, choose \textsf{Fill Matrix}.

\item[3.]  Select \textsf{Defined by Function.}

\item[4.]  Enter $g$ in the \textsf{Enter Function Name} box.

\item[5.]  Select 6 rows and 6 columns.

\item[6.]  Choose \textsf{OK}.

\item[7.]  Type $%
\limfunc{mod}6$ at the right of the matrix. (Type in mathematics mode; $mod$
will automatically turn gray.)

\item[8.]  Choose \textsf{Evaluate.\medskip }
\end{enumerate}

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 2 & 3 & 4 & 5 \\ 
0 & 2 & 4 & 6 & 8 & 10 \\ 
0 & 3 & 6 & 9 & 12 & 15 \\ 
0 & 4 & 8 & 12 & 16 & 20 \\ 
0 & 5 & 10 & 15 & 20 & 25
\end{array}
\right] \limfunc{mod}6=\left[ 
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 2 & 3 & 4 & 5 \\ 
0 & 2 & 4 & 0 & 2 & 4 \\ 
0 & 3 & 0 & 3 & 0 & 3 \\ 
0 & 4 & 2 & 0 & 4 & 2 \\ 
0 & 5 & 4 & 3 & 2 & 1
\end{array}
\right] \medskip $
\end{quotation}

You can also find this matrix as the product of a column matrix with a row
matrix.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{c}
0 \\ 
1 \\ 
2 \\ 
3 \\ 
4 \\ 
5
\end{array}
\right] \left[ 
\begin{array}{cccccc}
0 & 1 & 2 & 3 & 4 & 5
\end{array}
\right] =\left[ 
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 2 & 3 & 4 & 5 \\ 
0 & 2 & 4 & 6 & 8 & 10 \\ 
0 & 3 & 6 & 9 & 12 & 15 \\ 
0 & 4 & 8 & 12 & 16 & 20 \\ 
0 & 5 & 10 & 15 & 20 & 25
\end{array}
\right] \medskip $

$\left[ 
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 2 & 3 & 4 & 5 \\ 
0 & 2 & 4 & 6 & 8 & 10 \\ 
0 & 3 & 6 & 9 & 12 & 15 \\ 
0 & 4 & 8 & 12 & 16 & 20 \\ 
0 & 5 & 10 & 15 & 20 & 25
\end{array}
\right] \func{mod}6=\left[ 
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\ 
0 & 1 & 2 & 3 & 4 & 5 \\ 
0 & 2 & 4 & 0 & 2 & 4 \\ 
0 & 3 & 0 & 3 & 0 & 3 \\ 
0 & 4 & 2 & 0 & 4 & 2 \\ 
0 & 5 & 4 & 3 & 2 & 1
\end{array}
\right] \medskip $
\end{quotation}

\ 

Make a copy of this last matrix. From the \textsf{Edit} menu choose \textsf{%
Add Row(s)...}, add a new row at the top, choose \textsf{Add Column(s)}...,
add a new column at the left, and fill in the blanks to get the following
multiplication table modulo 6: 
\[
\begin{tabular}{c|cccccc}
$\times $ & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 
2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 
3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 
4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 
5 & 0 & 5 & 4 & 3 & 2 & 1
\end{tabular}
\]
From the table, we see that $2\cdot 4\limfunc{mod}6=2$ and $3\cdot 3\limfunc{%
mod}6=3$. (The extra horizontal and vertical lines were added for clarity,
but are not essential. To use these typesetting features, you must first
copy the matrix entries into a table, then revise the table.)

A more efficient way to generate the same multiplication table is to define $%
g(i,j)=(i-1)(j-1)\limfunc{mod}6$, then to add a row and a column to the
original matrix. A clever way to make this table is to define $g(i,j)=\left|
i-2\right| \left| j-2\right| $, choose \textsf{Fill Matrix} from the \textsf{%
Matrices} submenu, choose \textsf{Defined by Function} from the dialog box,
specify $g$ for the function, and set the matrix size to 7 rows and 7
columns. You can generate an addition table by defining $g(i,j)=i+j-2%
\limfunc{mod}6$.\medskip

\begin{example}
\label{Galois field}If $p$ is a prime, then the integers modulo $p$ form a 
\index{Field@Field}field, called a 
\index{Galois field@Galois field}\textsl{Galois field} and denoted $GF_{p}$.
For the prime $p=7$, you can generate the multiplication table by defining $%
g(i,j)=(i-1)(j-1)%
\limfunc{mod}7$ and choosing \textsf{Fill Matrix} from the \textsf{Matrix}
submenu, then selecting \textsf{Defined by function} from the dialog box.
You can generate the addition table in a similar manner using the function $%
f(i,j)=i+j-2\limfunc{mod}7$. 
\[
\begin{tabular}{c|ccccccc}
$\times $ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 
2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ 
3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ 
4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ 
5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ 
6 & 0 & 6 & 5 & 4 & 3 & 2 & 1
\end{tabular}
\quad \quad 
\begin{tabular}{c|ccccccc}
$+$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 
1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ 
2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ 
3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ 
4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 
5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ 
6 & 6 & 0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\]
\end{example}

\ 

\subsection{\ \label{Inverse modulo m}Inverses Modulo m}

If $ab\limfunc{mod}m=1$, then $b$ is called an 
\index{Inverse@Inverse!modulo m@modulo m}\textsl{inverse} of\ $a$\emph{\ }%
\textsl{modulo} $m,$ and we write $a^{-1}%
\limfunc{mod}m$ for the least positive residue of $b$.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$5^{-1}\limfunc{mod}7=3\medskip $
\end{quotation}

This calculation satisfies the definition of inverse, because $5\cdot 3%
\limfunc{mod}7=1$. Other notation for the inverse modulo $m$ includes $1/a%
\limfunc{mod}m$ and $\frac 1a\limfunc{mod}m.\medskip $

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$23^{-1}\limfunc{mod}257=190\vspace{6pt}$

$\frac{1}{5}\limfunc{mod}6=5\medskip $
\end{quotation}

\ 

The notation $a/b\limfunc{mod}m$ is interpreted as $a(b^{-1}\limfunc{mod}m)%
\limfunc{mod}m$; that is, find the inverse of $b$ modulo $m$, multiply the
result by $a,$ and then reduce the product modulo $m$.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$3/23\limfunc{mod}257=56\vspace{6pt}$

$\frac{2}{5}\limfunc{mod}6=4\medskip $
\end{quotation}

\ 

Note that $a^{-1}\limfunc{mod}m$ exists if and only if $a$ is 
\index{Relatively prime@Relatively prime}\label{Relatively prime}\textsl{%
relatively prime} to $m$; that is, it exists if and only if $\gcd (a,m)=1$.
Thus, modulo $6$, only $1$ and $5$ have inverses. Modulo any prime, every
nonzero residue has an inverse. In terms of the multiplication table modulo $%
m$, the integer $a$ has an inverse modulo $m$ if and only if $1$ appears in
row $a%
\limfunc{mod}m$ (and $1$ appears in column $a\limfunc{mod}m$).\medskip

\subsection{\ \label{Solving congruences}Solving Congruences Modulo m}

To 
\index{Solving congruences@Solving congruences}solve a congruence of the
form $ax\equiv b\,\left( 
\limfunc{mod}m\right) $, multiply both sides by $a^{-1}\limfunc{mod}m$ to
get $x=b/a\limfunc{mod}m$.

The congruence $17x\equiv 23\,\left( \limfunc{mod}127\right) $ has a
solution $x=91,$ as the following steps illustrate.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$23/17\limfunc{mod}127=\allowbreak 91\medskip $
\end{quotation}

Check this result by substitution back into the original congruence.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$17\cdot 91\,\limfunc{mod}127\medskip =\allowbreak 23$
\end{quotation}

Note that, since $91$ is a solution to the congruence $17x\equiv
23\,\,\left( \limfunc{mod}127\right) $, additional solutions are given by $%
91+127n$, where $n$ is any integer. In fact, $x\equiv 91\,\left( \limfunc{mod%
}127\right) $ is just another way of writing $x=91+127n$ for some integer $n$%
.\medskip

\subsection{\ \label{Pairs of congruences}Pairs of Linear Congruences}

Since linear congruences of the form $ax\equiv b\,\left( \limfunc{mod}%
m\right) $ can be reduced to simple congruences of the form $x\equiv
c\,\left( \limfunc{mod}m\right) $, we consider systems of congruences in
this latter form.\medskip

\begin{example}
Consider the system of two congruences 
\begin{eqnarray*}
x &\equiv &45\,\left( \limfunc{mod}237\right) \\
x &\equiv &19\,\left( \limfunc{mod}419\right)
\end{eqnarray*}
Checking, $\gcd (237,419)=\,1$, so $237$ and $419$ are relatively prime. The
first congruence can be rewritten in the form $x=45+237k$ for some integer $%
k $. Substituting this value into the second congruence, we see that 
\[
45+237k=19+419r 
\]
for some integer $r$. This last equation can be rewritten in the form $%
237k=19-45\limfunc{mod}419$, which has the solution 
\[
k=(19-45)/237\limfunc{mod}419=60 
\]
Hence, 
\[
x=45+237\cdot 60=14265 
\]
Checking, $14265\limfunc{mod}237=45$ and $14265\limfunc{mod}419=19$.
\end{example}

\strut

\begin{example}
The complete set of solutions is given by 
\[
x=14265+237\cdot 419s\equiv 14265\,\left( \limfunc{mod}99303\right) 
\]
Thus, the original pair of congruences has been reduced to a single
congruence, 
\[
x\equiv 14265\,\left( \limfunc{mod}99303\right) 
\]
\end{example}

In general, if $m$ and $n$ are relatively prime, then a solution to the pair 
\begin{eqnarray*}
x &\equiv &a\,\left( \limfunc{mod}m\right) \\
x &\equiv &b\,\left( \limfunc{mod}n\right)
\end{eqnarray*}
is given by 
\[
x=a+m\left[ (b-a)/m\limfunc{mod}n\right] 
\]
A complete set of solutions is given by 
\[
x=a+m\left[ (b-a)/m\limfunc{mod}n\right] +rmn 
\]
where $r$ is an arbitrary integer.\medskip

\subsection{\ \label{Systems of congruences}Systems of Linear Congruences%
\label{Chinese remainder theorem}}

You can reduce systems of any number of congruences to a single congruence
by solving systems of congruences two at a time. The \textsl{Chinese
remainder theorem} states 
\index{Chinese remainder theorem@Chinese remainder theorem}that, if the
moduli are relatively prime in pairs, then there is a unique solution modulo
the product of all the moduli.\medskip

\begin{example}
Consider the 
\index{Systems of congruences@Systems of congruences}system of three linear
congruences 
\begin{eqnarray*}
x &\equiv &45\,\left( 
\limfunc{mod}237\right) \\
x &\equiv &19\,\left( \limfunc{mod}419\right) \\
x &\equiv &57\,\left( \limfunc{mod}523\right)
\end{eqnarray*}
Checking, $\gcd (237\cdot 419,523)=\,1$; hence this system has a solution.
The first two congruences can be replaced by the single congruence $x\equiv
14265\,\left( \limfunc{mod}99303\right) $; hence the three congruences can
be replaced by the pair 
\begin{eqnarray*}
x &\equiv &14265\,\left( \limfunc{mod}99303\right) \\
x &\equiv &57\,\left( \limfunc{mod}523\right)
\end{eqnarray*}
As before, $14265+99303k=57+523r$ for some integers $k$ and $r$. Thus, $%
k=\left( 57-14265\right) /99303\limfunc{mod}523=134$; hence $%
x=14265+99303\cdot 134=\,13320867$. This system of three congruences can
thus be reduced to the single congruence 
\[
x\equiv 13320867\left( \limfunc{mod}\,51935469\right) 
\]
\end{example}

\ 

\subsection{\ \label{Extended precision arithmetic}Extended Precision
Arithmetic}

Computer algebra systems support exact sums and products of integers that
are hundreds of digits long. One way to do such 
\index{Extended precision@Extended precision arithmetic}extended precision
arithmetic is to generate a set of mutually relatively prime bases, and to
do modular arithmetic modulo all of these bases. For example, consider the
vector 
\[
\left( 997,999,1000,1001,1003,1007,1009\right) 
\]
of bases. Factorization shows that the entries are pairwise relatively
prime.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Factor%
\vspace{4pt}}
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{c}
997 \\ 
999 \\ 
1000 \\ 
1001 \\ 
1003 \\ 
1007 \\ 
1009
\end{array}
\right] =\left[ 
\begin{array}{c}
997 \\ 
3^{3}37 \\ 
2^{3}5^{3} \\ 
7\times 11\times 13 \\ 
17\times 59 \\ 
19\times 53 \\ 
1009
\end{array}
\right] \medskip $
\end{quotation}

Consider the two numbers $23890864094$ and $1883289456$. You can represent
these numbers by reducing the numbers modulo each of the bases. Thus,

\begin{eqnarray*}
23890864094 &\longleftrightarrow &\left[ 
\begin{array}{rl}
23890864094\limfunc{mod}\;997 & =350 \\ 
23890864094\limfunc{mod}\;999 & =872 \\ 
23890864094\limfunc{mod}1000 & =\,\;94 \\ 
23890864094\limfunc{mod}1001 & =\,\;97 \\ 
23890864094\limfunc{mod}1003 & =879 \\ 
23890864094\limfunc{mod}1007 & =564 \\ 
23890864094\limfunc{mod}1009 & =218
\end{array}
\right] \\
&&\vspace{1pt} \\
1883289456 &\longleftrightarrow &\left[ 
\begin{array}{rl}
1883289456\limfunc{mod}\;997 & =324 \\ 
1883289456\limfunc{mod}\;999 & =630 \\ 
1883289456\limfunc{mod}1000 & =456 \\ 
1883289456\limfunc{mod}1001 & =\;48 \\ 
1883289456\limfunc{mod}1003 & =488 \\ 
1883289456\limfunc{mod}1007 & =70 \\ 
1883289456\limfunc{mod}1009 & =37
\end{array}
\right] \vspace{6pt}
\end{eqnarray*}
Thus, the product $23890864094\cdot 1883289456$ is represented by the vector 
\[
\left[ 
\begin{array}{rl}
350\cdot 324\limfunc{mod}\;997 & =\;739 \\ 
872\cdot 630\limfunc{mod}\;999 & =\;909 \\ 
94\cdot 456\limfunc{mod}1000 & =\;864 \\ 
97\cdot 48\limfunc{mod}1001 & =\;652 \\ 
879\cdot 488\limfunc{mod}1003 & =\;671 \\ 
564\cdot 70\limfunc{mod}1007 & =\;207 \\ 
218\cdot 37\limfunc{mod}1009 & =1003
\end{array}
\right] \vspace{6pt} 
\]
The product $23890864094\cdot 1883289456$ is now a solution to the system 
\begin{eqnarray*}
x &\equiv &739\,\left( \limfunc{mod}997\right) \\
x &\equiv &909\left( \limfunc{mod}999\right) \\
x &\equiv &864\left( \limfunc{mod}1000\right) \\
x &\equiv &652\,\left( \limfunc{mod}1001\right) \\
x &\equiv &671\,\left( \limfunc{mod}1003\right) \\
x &\equiv &207\,\left( \limfunc{mod}1007\right) \\
x &\equiv &1003\left( \limfunc{mod}1009\right)
\end{eqnarray*}

\ 

\subsection{\ Powers Modulo m\label{Powers modulo m}}

\begin{quote}
$\blacktriangleright $ To calculate large 
\index{Powers modulo m@Powers modulo m}powers modulo $m$
\end{quote}

\begin{itemize}
\item  \textsf{Evaluate} $a^{n}%
\limfunc{mod}m$.\medskip
\end{itemize}

Define $a=2789596378267275$, $n=3848590389047349$, and $m=2838490563537459$%
.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$a^{n}\limfunc{mod}m=\allowbreak 26220\,18141\,09828\medskip $
\end{quotation}

\textsl{Fermat's Little Theorem } 
\index{Fermat's little theorem@Fermat's little theorem}\label%
{Fermat's little theorem}states that, if $p$ is prime and $0<a<p$, then 
\[
a^{p-1}%
\limfunc{mod}p=1 
\]
The integer 1009 is prime, and the following is no surprise.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$2^{1008}\limfunc{mod}1009=\allowbreak 1$
\end{quotation}

\ 

\subsection{\ Generating 
\index{Large primes@Large primes}\label{Large primes}Large Primes\label%
{Prime numbers}}

\textsl{Scientific Notebook} does not have a built-in function to generate
large primes, 
\index{Prime numbers@Prime numbers}but the underlying computational system
does. The following is an example of how to define \textsl{Scientific
Notebook} functions that correspond to existing functions in the underlying
computational system. 
\index{Maple functions@Maple functions}\label{Maple functions}(See the
Appendix for a general discussion of how to access such functions.) 
\index{Automatic substitution@Automatic substitution}\label%
{Automatic substitution (2)}In this example, 
\index{Nextp@Nextp}\label{Next prime}$p(x)$is defined as the \textsl{%
Scientific Notebook} name for the Maple function, \textbf{nextprime(x)},
which generates the next larger prime.\medskip

\begin{quote}
$\blacktriangleright $ To define $p(x)$ as the next prime function
\end{quote}

\begin{enumerate}
\item[1.]  From the \textsf{Define }submenu, choose \textsf{Define Maple Name%
}.%
\FRAME{dtbpF}{3.7663in}{2.4993in}{0pt}{}{}{defmapnm.wmf}{\special{language
"Scientific Word";type "GRAPHIC";display "PICT";valid_file "F";width
3.7663in;height 2.4993in;depth 0pt;original-width 268.75pt;original-height
177.6875pt;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'DefMapNm.wmf';file-properties "XNPEU";}}

\item[2.]  Enter nextprime(x) as the Maple Name.

\item[3.]  Enter $p(x)$ as the Scientific Notebook Name.

\item[4.]  Click \textsf{OK}. (Leave other options blank.)
\end{enumerate}

Test the function using Evaluate.

\begin{quote}
$\blacktriangleright $ Evaluate
\end{quote}

\begin{quotation}
$p(4)=\allowbreak 5$

$p(500)=\allowbreak 503$

$p(8298)=\allowbreak 8311$

$p\left( 273849728952758923\right) =\allowbreak 273\,84972\,89527\,58939$
\end{quotation}

\ 

\begin{example}
The 
\index{RSA algorithm@RSA algorithm}Rivest-Shamir-Adleman (RSA) \label%
{RSA algorithm}cipher system is based directly on Euler's theorem and
requires a pair of large primes. First, generate a pair of large
primes---say, 
\[
q=p(20934834573)=20934834647 
\]
and 
\[
r=p\left( 2593843747347\right) =2593843747457 
\]
(In practice, larger primes are used; say, $q\approx 10^{100}$ and $r\approx
10^{100}$.) Then 
\begin{eqnarray*}
n &=&qr \\
&=&20934834647\cdot 2593843747457 \\
&=&\,543\,01689\,95316\,71217\,42679
\end{eqnarray*}
and the number of positive integers $\leq n$ and relatively prime to $n$ is
given by 
\begin{eqnarray*}
\varphi (n) &=&(q-1)(r-1) \\
&=&20934834646\cdot 2593843747456 \\
&=&\,543\,01689\,95055\,23431\,60576
\end{eqnarray*}
\label{Ciphertext}\label{Plaintext}Let $x=29384737849576728375$ be 
\index{Plaintext@Plaintext}plaintext (suitably generated by a short section
of English text). Long messages must be broken up into small enough chunks
that each plaintext integer $x$ is smaller than the modulus $n$. Choose $E$
to be a moderately large positive integer that is relatively prime to $%
\varphi (n)$, say $E=1009$. The 
\index{Ciphertext@Ciphertext}ciphertext is given by 
\[
y=x^{E}%
\limfunc{mod}n=20636340188476258131729 
\]
Let 
\[
D=1009^{-1}\limfunc{mod}\varphi (n)=4251569381658706748945 
\]
Then friendly colleagues can recover the plaintext by calculating 
\[
z=y^{D}\limfunc{mod}n=29384737849576728375 
\]
\medskip
\end{example}

\subsection{\ Related topics}

\begin{itemize}
\item  \hyperref{Elementary Number Theory}{}{}{DM2-2.tex#Prime factorization}

\item  \hyperref{Solving Equations}{}{}{DM12-1.tex#Integer solutions}

\item  \hyperref{Other Systems Modulo m}{}{}{DM12-3.tex#Matrices modulo m}

\item  \hyperref{Polynomials Modulo Polynomials}{}{}{DM12-4.tex#Polynomials
modulo polynomials}

\item  \hyperref{Linear Programming}{}{}{DM12-5.tex#Linear programming}

\item  \hyperref{Exercises and Solutions}{}{}{DM12-6.tex#Exercises}
\end{itemize}

\rule{0.67in}{0.01in}

\hyperref{\FRAME{itbpF}{0.5275in}{0.3399in}{0.0519in}{}{}{index.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";display "PICT";valid-file
"F";width 0.5275in;height 0.3399in;depth 0.0519in;original-width
36.125pt;original-height 22.5625pt;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'index.wmf';file-properties "XNPEU";}}}{}{}{%
DMIndex.tex#Math Index}\quad {\small Index entries: \hyperref{Applied modern
algebra}{}{}{DMIndex.tex#Applied modern algebra}, \hyperref{Congruence}{}{}{%
DMIndex.tex#Congruence}, \hyperref{Solve}{}{}{DMIndex.tex#Solve}}

\end{document}
