CoCalc Public Fileswww / 168 / refs / stein-numthry.tex
Author: William A. Stein
Compute Environment: Ubuntu 18.04 (Deprecated)
1\documentclass{report}
2\bibliographystyle{amsalpha}
3
4%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6%%
7%%  FILE:  ent.tex
8%%          -- Elementary Number Theory and Elliptic Curves
9%%
10%%  (c) 2004 -- , William Stein ([email protected])
11%%
12%%  Under contract to publish with Springer-Verlag.
13%%
14%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16
17\usepackage{svsing2e}
18\usepackage{amsfonts}
19\usepackage{amsmath}
20\usepackage{amssymb}
21\usepackage{amsopn}
22\usepackage{amsthm}
23\usepackage{fancybox}
24\usepackage{makeidx}
25\usepackage{graphicx}
26\usepackage{psfrag}
27\usepackage{pstricks}
28\usepackage{python}
29\usepackage[hypertex]{hyperref}
30%\usepackage[hyperindex,pdfmark]{hyperref}
31
32\newcommand{\edit}[1]{}
33
34\numberwithin{section}{chapter}
35\numberwithin{equation}{section}
36\newcommand{\todo}[1]{{[[{\bf #1}]]}}
37
38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
39%% Operators and macros
40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41\DeclareMathOperator{\Div}{Div}
42\DeclareMathOperator{\Li}{Li}
43\DeclareMathOperator{\SL}{SL}
44\DeclareMathOperator{\ind}{ind}
45\DeclareMathOperator{\lcm}{lcm}
46\DeclareMathOperator{\new}{new}
47\DeclareMathOperator{\ord}{ord}
48\DeclareMathOperator{\tor}{tor}
49\DeclareMathOperator{\ur}{ur}
50\renewcommand{\i}[1]{\index{#1}}
51\newcommand{\ii}[1]{#1\index{#1}}
52\newcommand{\defn}[1]{{\em #1}\index{#1|nn}}
53\newcommand{\ithm}[1]{\index{theorem!#1}\index{#1 theorem}}
54\newcommand{\iprop}[1]{\index{proposition!#1}\index{#1 proposition}}
55\newcommand{\icor}[1]{\index{corollary!#1}\index{#1 corollary}}
56\newcommand{\C}{\mathbb{C}}
57\newcommand{\D}{{\mathbb D}}
58\newcommand{\F}{\mathbb{F}}
59\newcommand{\Gam}{\Gamma}
60\newcommand{\N}{\mathbb{N}}
61\newcommand{\Q}{\mathbb{Q}}
62\newcommand{\R}{\mathbb{R}}
63\newcommand{\Z}{\mathbb{Z}}
64\newcommand{\abcd}[4]{%
65      \left(\begin{smallmatrix}#1&#2\\#3&#4%
66            \end{smallmatrix}\right)}
67\newcommand{\abs}[1]{\left|#1\right|}
68\newcommand{\alp}{\alpha}
69%\newcommand{\assign}{\leftarrow}
70\newcommand{\assign}{=}
71\newcommand{\con}{\equiv}
72\newcommand{\cross}{\times}
73\newcommand{\da}{\downarrow}
74\newcommand{\ds}{\displaystyle}
75\newcommand{\eps}{\varepsilon}
76\newcommand{\exref}[2]{Exercise~\ref{#1}.\ref{#2}}
77\newcommand{\e}{\mathbf{e}}
78\newcommand{\hd}[1]{\vspace{1ex}\noindent{\bf #1} }
79\newcommand{\hra}{\hookrightarrow}
80\newcommand{\h}{\mathfrak{h}}
81\newcommand{\intersect}{\cap}
82\newcommand{\isom}{\cong}
83\newcommand{\kr}[2]{\left(\frac{#1}{#2}\right)}
84\newcommand{\la}{\leftarrow}
85\newcommand{\lra}{\longrightarrow}
86\newcommand{\m}{\mathfrak{m}}
87\newcommand{\ncisom}{\approx}
88\newcommand{\p}{\mathfrak{p}}
89\newcommand{\q}{\mathbf{q}}
90\newcommand{\ra}{\rightarrow}
91\newcommand{\set}[1]{\{#1\}}
92\newcommand{\ul}[1]{\underline{#1}}
93\newcommand{\union}{\cup}
94\newcommand{\vphi}{\varphi}
95\newcommand{\zmod}[1]{\Z/#1\Z{}}
96\renewcommand{\L}{\mathcal{L}}
97\renewcommand{\O}{\mathcal{O}}
98\renewcommand{\P}{\mathbb{P}}
99\renewcommand{\Re}{\mbox{\rm Re}}
100\renewcommand{\a}{\mathfrak{a}}
101\renewcommand{\l}{\ell}
102\renewcommand{\mathbb}{\mathbf}
103\renewcommand{\t}{\tau}
104\newcommand{\nn}[1]{{\bf #1}} % used for primary ref in index
105
106
107%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
108%% Theorem styles
109%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
110\theoremstyle{plain}
111\newtheorem{theorem}{Theorem}[section]
112\newtheorem{joke}[theorem]{Joke}
113\newtheorem{proposition}[theorem]{Proposition}
114\newtheorem{corollary}[theorem]{Corollary}
115\newtheorem{claim}[theorem]{Claim}
116\newtheorem{lemma}[theorem]{Lemma}
117\newtheorem{conjecture}[theorem]{Conjecture}
118\newtheorem{openproblem}[theorem]{Open Problem}
119
120\theoremstyle{definition}
121\newtheorem{alg}[theorem]{Algorithm}
122\newtheorem{listing}[theorem]{Listing}
123\newtheorem{definition}[theorem]{Definition}
124\newtheorem{question}[theorem]{Question}
125\newtheorem{problem}[theorem]{Problem}
126
127\theoremstyle{remark}
128\newtheorem{goal}[theorem]{Goal}
129\newtheorem{remark}[theorem]{Remark}
130\newtheorem{example}[theorem]{Example}
131\newtheorem{exercise}[theorem]{Exercise}
132
133
134%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
135%% Environments
136%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
137\newenvironment{algorithm}[1]{%
138\begin{alg}[#1]\index{algorithm!#1}\sf
139}%
140{\end{alg}}
141\newenvironment{steps}%
142{\begin{enumerate}\setlength{\itemsep}{0.1ex}}{\end{enumerate}}
143
144\newenvironment{exercises}
145{\section{Exercises}
146 \renewcommand{\labelenumi}{\thechapter.\theenumi}
147  \begin{enumerate}
148}{\end{enumerate}}
149
150\newenvironment{solutions}[2]
151{\section*{Chapter~\ref{#1}}\newcommand{\chap}{#2}
152  %\renewcommand{\labelenumi}
153  \begin{enumerate}
154}{\end{enumerate}}
155
156
157\author{William Stein}
158\title{Elementary Number Theory}
159\date{October 2005}
160\makeindex
161
162\setcounter{tocdepth}{1}
163
164\begin{document}
165\maketitle
166\newpage
167\mbox{}
168\vspace{2in}
169\begin{center}
170To my students and my wife, Clarita Lefthand.
171\end{center}
172\newpage
173\tableofcontents
174\pagenumbering{arabic}
175
176%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
177%%
178%% Chapter: Preface
179%%
180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
181
182\chapter*{Preface}
184
185This is a textbook about prime
186numbers, congruences, basic public-key cryptography, quadratic
187reciprocity, continued fractions, elliptic curves, and number
188theory algorithms.  We assume the
189reader has some familiarity with groups, rings, and fields, and
190for Chapter~\ref{ch:computing} some programming experience.
191This book grew out of an undergraduate course that the
192author taught at Harvard University in 2001 and 2002.
193
194
195
196\vspace{1.5ex}\noindent{}{\bf Notation and Conventions.}
197We let $\N=\{1,2,3,\ldots\}$ denote the natural numbers, and use the
198standard notation $\Z$, $\Q$, $\R$, and $\C$ for the rings of integer,
199rational, real, and complex numbers, respectively.\index{notation} In
200this book we will use the words proposition, theorem, lemma, and
201corollary as follows.  Usually a proposition is a less important or
202less fundamental assertion, a theorem a deeper culmination of ideas, a
203lemma something that we will use later in this book to prove a
204proposition or theorem, and a corollary an easy consequence of a
205proposition, theorem, or lemma.
206
207\vspace{1.5ex}\noindent{}{\bf Acknowledgements.} Brian Conrad and Ken
209throughout the book.  Baurzhan Bektemirov, Lawrence Cabusora, and
211Frank Calegari used the course when teaching Math 124 at Harvard,
212and he and his students provided much feedback.
214\exref{ch:reciprocity}{ex:rec8}.  Seth Kleinerman wrote a version of
215Section~\ref{sec:contfrac_e} as a class project.
218Samit Dasgupta, George Stephanides,
219Kevin Stern, and Heidi
220Williams all suggested corrections.  I also benefited from
221conversations with Henry Cohn and David Savitt.
222I used Emacs, \LaTeX, and Python in the preparation of this book.
223
224% Stephanides of University of Macedonia
225%[email protected]
226
227%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
228%%
229%% Chapter: Prime Numbers
230%%
231%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
232
233\chapter{Prime Numbers}
234\label{ch:primes}
235
236
237In Section~\ref{sec:fundamental_thm} we describe how the integers are
238built out of the prime numbers $2, 3, 5, 7, 11,\ldots$.  In
239Section~\ref{sec:primeseq} we discuss theorems about the set of primes
240numbers\index{primes}, starting with Euclid's\index{Euclid} proof that
241this set is infinite, then explore the distribution of primes via the
242prime number theorem and the Riemann Hypothesis (without proofs).
243
244\section{Prime Factorization}
245\label{sec:fundamental_thm}
246\subsection{Primes}\label{sec:primes}
247The set of {\em natural numbers}\index{natural numbers} is
248$$249 \N = \{1,2,3,4,\ldots\}, 250$$
251and the set of {\em integers}\index{integers} is
252$$253 \Z = \{\ldots, -2, -1, 0, 1,2,\ldots\}. 254$$
255% \begin{remark}
256% One reason the integers are denoted by~$\Z$ is because the German word
257% for the integers is Zahlen\index{Zahlen}.
258% \end{remark}
259
260% The integers~$\Z$ are an example of a structure called a commutative ring.
261% \begin{definition}[Commutative Ring]\label{defn:ring}
262% A \defn{commutative ring} is a set~$R$ equipped with binary operations
263% $+:R\times R \to R$ and $\times:R\times R \to R$ such that
264% $(R,+)$ is an abelian group, $\times$ is associative and commutative,
265% and for any $x,y,z\in R$ we have $x\times (y+z)=x\times y+x \times z$.
266% We assume that $R$ contains an element $1$ such that $1x=x$ for
267% all $x\in R$.
268% \end{definition}
269% The rational numbers, the real numbers, and the complex numbers are
270% all also rings, but the set of natural numbers is not a ring, since
271% $(\N,+)$ is not a group, e.g., because~$2$ does not have an additive
272% inverse.
273
274% We will not consider any non-commutative rings in this
275% book, so the phrase let~$R$ be a ring'' will always mean that~$R$ is
276% a commutative ring as defined above.
277
278
279\begin{definition}[Divides]
280If $a, b\in \Z$ we say that~$a$
281\defn{divides}~$b$, written $a\mid b$, if $ac=b$ for some
282$c\in \Z$.  In this case we say~$a$ is a \defn{divisor} of~$b$.  We say
283that~$a$ \defn{does not divide}~$b$, written $a\nmid b$, if there is no
284$c\in \Z$ such that $ac=b$.
285\end{definition}
286For example, we have $2 \mid 6$ and $-3\mid 15$.
287Also, all integers divide\index{divides}~$0$, and~$0$ divides
288only~$0$.  However, $3$ does not divide $7$ in $\Z$.
289
290\begin{remark}
291  The notation $b \overset{\ds .}{:}\! a$ for $b$ is divisible by
292  $a$'' is common in Russian literature on number theory.
293\end{remark}
294
295% In order to formulate the definition of prime numbers, it will
296% be useful to have the notion of unit.
297% \begin{definition}[Unit]\label{defn:unit}
298% A \defn{unit} is$299% that has a multiplicative inverse, i.e., for which there exists 300%$y\in R$such that$xy=1$. 301% \end{definition} 302% The units of the ring~$\Z$of integers are$\pm 1$, since 303% the inverses of all other (nonzero) integers are in$\Q$and not in 304%$\Z$. 305 306% \begin{definition}[Irreducible]\label{defn:irred} 307% Let$R$be a ring and suppose$x\in R$is not a unit. Then~$x$is 308% \defn{irreducible} if whenever$x=yz$with$y,z\in R$, then~$y$309% or~$z$is a unit. 310% \end{definition} 311% For example, the integer$2\in \Z$is irreducible, because if$2=xy$, 312% with$x,y\in\Z$, then one of$x$or$y$must be$\pm 1$(there are 313% just a few possibilities to check, since if$|x|>2$or$|y|>2$, then 314%$|xy| > 2$). The integer~$6$is not irreducible because$6=2\cdot 3$, 315% and neither~$2$nor~$3$is a unit. 316 317% We introduce notion of ideal in order to define primality 318% for elements of a ring. 319% \begin{definition}[Ideal]\label{defn:ideal} 320% A subset$I$of a ring~$R$is an \defn{ideal} 321% if$I$is closed under addition and if whenever 322%$x\in R$and$y\in I$, then$xy\in I$. 323% \end{definition} 324% For example, if$x$is any element of$R$then 325% $$326% xR = (x) = \{xy: y \in R\} 327%$$ 328% is easily seen to be an ideal because~$R$is commutative. 329% We call it the \defn{ideal generated by}~$x$. 330% The sets$\{0\}$and$R$are also ideals of$R$, 331% called the \defn{zero ideal} and \defn{unit ideal}, respectively. 332 333% \begin{definition}[Prime Ideal] 334% An ideal~$I\neq R$of a ring$R$is a \defn{prime ideal} if 335% whenever$xy\in I$then either$x\in I$or$y\in I$. 336% \end{definition} 337 338% \begin{definition}[Prime Element]\label{defn:prime} 339% An element~$x$of a ring~$R$is \defn{prime} if the ideal$xR$340% generated by~$x$is prime. 341% \end{definition} 342% Unwinding the definitions, we see that an element$x\in R$is prime if 343% whenever$a, b\in R$and$x\mid ab$, then$x\mid a$or$x\mid b$. 344 345\begin{definition}[Prime and Composite]\label{defn:prime_composite} 346An integer$n>1$is \defn{prime} if it the only positive 347divisors of$n$are$1$and~$n$. 348We call~$n$\defn{composite} if~$n$is not prime. 349\end{definition} 350 351% Suppose$n>1$is a natural number. 352% Theorem~\ref{thm:euclid} below asserts that~$n$is prime if and only 353% if~$n$is irreducible; equivalently,~$n$is prime if and only if~$1$354% and~$n$are the only positive divisors of~$n$. 355 356The number~$1$is neither prime nor composite. The first few 357primes of~$\N$are $$3582,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 35947, 53, 59, 61, 67, 71, 73, 79, \ldots,$$ 360and the first few 361composites are $$3624,6,8,9,10,12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 36326, 27, 28, 30, 32, 33, 34, \ldots.$$ 364 365\begin{remark} 366 J.\thinspace{}H. Conway argues in \cite[viii]{conway:sensual} that 367$-1$should be considered a prime, and in the 1914 table 368 \cite{lehmer:primetable}, Lehmer considers~$1$to be a prime. 369In this book we consider neither$-1$nor$1$to be prime. 370\end{remark} 371 372Every natural number is built, in a unique way, out of prime numbers: 373\begin{theorem}[Fundamental Theorem of Arithmetic]\label{thm:fundamental}% 374\index{fundamental theorem of arithmetic}% 375\index{integers!factor uniquely}% 376\ithm{unique factorization}% 377Every natural number can be written as a product of primes 378uniquely up to order. 379\end{theorem} 380Note that primes are the products with only one factor and~$1$is the 381empty product. 382 383\begin{remark} 384Theorem~\ref{thm:fundamental}, which we will prove in 385Section~\ref{sec:proof_fundamental}, is trickier to prove than you 386might first think. For example, unique factorization\index{unique 387factorization} fails in the ring 388$$389 \Z[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b\in\Z\} \subset \C, 390$$ 391where~$6$factors into irreducible elements in two different ways: 392$$393 2\cdot 3 = 6 = (1+\sqrt{-5})\cdot (1-\sqrt{-5}). 394$$ 395\end{remark} 396 397\subsection{The Greatest Common Divisor}\index{greatest common divisor} 398\index{gcd} 399We will use the notion of greatest common divisor of two integers to 400prove that if~$p$is a prime and$p\mid ab$, then$p\mid a$or$p\mid
401b$. Proving this is the key step in our proof of 402Theorem~\ref{thm:fundamental}. 403 404\begin{definition}[Greatest Common Divisor] 405Let 406$$407 \gcd(a,b)=\max\left\{d\in \Z : d \mid a\text{ and } d\mid b\right\}, 408$$ 409unless both~$a$and~$b$are~$0$in which case 410$\gcd(0,0)=0$. 411\end{definition} 412For example, 413$\gcd(1,2)=1$, 414$\gcd(6,27)=3$, and 415for any~$a$, 416$\gcd(0,a)=\gcd(a,0)=a$. 417 418If$a\neq 0$, the greatest common divisor exists because if$d\mid a$419then$d\leq a$, and there are only$a$positive integers$\leq a$. 420Similarly, the$\gcd$exists when$b\neq 0$. 421 422\begin{lemma}\label{lem:gcdprops} 423For any integers$a$and$b$we have 424$$425 \gcd(a,b)= \gcd(b,a) = \gcd(\pm a, \pm b) = \gcd(a,b-a) = \gcd(a,b+a). 426$$ 427\end{lemma} 428\begin{proof} 429 We only prove that$\gcd(a,b) = \gcd(a,b-a)$, since the other cases 430are proved in a similar way. Suppose$d\mid a$and 431$d\mid b$, so there exist integers$c_1$and$c_2$such that$dc_1 =
432  a$and$dc_2 = b$. Then$b - a = dc_2 - dc_1 = d(c_2-c_1)$, so 433$d\mid b-a$. Thus$\gcd(a,b)\leq \gcd(a,b-a)$, since the set over 434 which we are taking the max for$\gcd(a,b)$is a subset of the set 435 for$\gcd(a,b-a)$. The same argument with$a$replaced by$-a$436 and$b$replaced by$b-a$, shows that$\gcd(a,b-a)=\gcd(-a,b-a)\leq
437  \gcd(-a,b)=\gcd(a,b)$, which proves that$\gcd(a,b)=\gcd(a,b-a)$. 438\end{proof} 439 440\begin{lemma}\label{lem:gcdprops2} 441Suppose$a,b,n\in\Z$. Then 442$\gcd(a,b) = \gcd(a,b-an)$. 443\end{lemma} 444\begin{proof} 445By repeated application of Lemma~\ref{lem:gcdprops}, we have 446$$447 \gcd(a,b) = \gcd(a,b-a) = \gcd(a,b-2a) = \cdots = \gcd(a,b-2n). 448$$ 449\end{proof} 450 451Assume for the moment that we have already proved 452Theorem~\ref{thm:fundamental}. A natural (and naive!) way to compute 453$\gcd(a,b)$is to factor~$a$and~$b$as a product of primes using 454Theorem~\ref{thm:fundamental}; then the prime factorization of 455$\gcd(a,b)$can read off from that of$a$and$b$. For example, if 456$a=2261$and$b=1275$, then$a=7\cdot {\bf 17}\cdot 19$and$b=3\cdot
4575^2\cdot {\bf 17}$, so$\gcd(a,b) = 17$. It turns out that the 458greatest common divisor of two integers, even huge numbers (millions 459of digits), is surprisingly easy to compute using 460Algorithm~\ref{alg:gcd} below, which computes$\gcd(a,b)$without 461factoring~$a$or~$b$. \index{compute!greatest common divisor} 462 463To motivate Algorithm~\ref{alg:gcd}, we compute$\gcd(2261,1275)$in 464a different way. First, we recall a helpful fact. 465\begin{proposition}\label{prop:division}\iprop{long division} 466 Suppose that~$a$and~$b$are integers with$b\neq 0$. Then there 467 exists unique integers~$q$and~$r$such that$0\leq r< |b|$and$a =
468  bq + r$. 469\end{proposition} 470\begin{proof} 471 For simplicity, assume that both~$a$and~$b$are positive (we leave 472 the general case to the reader). Let$Q$be the set of all 473 nonnegative integers$n$such that$a-bn$is nonnegative. Then$Q$474 is nonempty because$0\in Q$and$Q$is bounded because$a-bn<0$for 475 all$n>a/b$. Let$q$be the largest element of~$Q$. Then$r=a-bq <
476  b$, otherwise$q+1$would also be in~$Q$. Thus~$q$and~$r$satisfy 477 the existence conclusion. 478 479 To prove uniqueness, suppose for the sake of contradiction that$q'$480 and$r'=a-bq'$also satisfy the conclusion but that$q'\neq q$. Then 481$q'\in Q$since$r'=a-bq'\geq 0$, so$q'<q$and we can write 482$q'=q-m$for some$m>0$. But then$r' = a-bq' = a-b(q-m) = a-bq +
483  bm = r + bm > b$since$r\geq 0$, a contradiction. 484\end{proof} 485 486For us an \defn{algorithm} is a finite sequence of instructions that 487can be followed to perform a specific task, such as a sequence of 488instructions in a computer program, which must terminate on 489any valid input. The word algorithm'' is sometimes used more 490loosely (and sometimes more precisely) than defined here, but this 491definition will suffice for us. 492 493\begin{algorithm}{Division Algorithm}\label{alg:division}% 494\index{division algorithm} 495 Suppose$a$and$b$are integers with$b\neq 0$. This algorithm 496computes integers$q$and$r$such that$0\leq r<|b|$and 497$a=bq+r$. We will not describe the actual steps of this algorithm, 498since it is just the familiar long division algorithm. 499\end{algorithm} 500 501We use the division algorithm repeatedly to compute 502$\gcd(2261,1275)$. Dividing$2261$by$1275$we find that 503$$504 2261 = 1\cdot 1275 + 986, 505$$ 506so$q=1$and$r=986$. 507Notice that if a natural number~$d$divides both$2261$and$1275$, 508then~$d$divides their difference$986$and~$d$still divides$1275$. 509On the other hand, if~$d$divides both$1275$and$986$, then it has 510to divide their sum$2261$as well! We have made progress: 511$$\gcd(2261,1275) = \gcd(1275,986).$$ 512This equality also follows by repeated application of 513Lemma~\ref{lem:gcdprops}. 514Repeating, we have 515$$1275 = 1\cdot 986 + 289,$$ 516so$\gcd(1275,986)=\gcd(986,289). 517Keep going: 518\begin{align*} 519986&=3\cdot 289 + 119\\ 520289&=2\cdot 119 + 51\\ 521119&=2\cdot 51 + 17. 522\end{align*} 523Thus\gcd(2261,1275)=\cdots=\gcd(51,17)$, which is$17$524because$17\mid 51$. Thus 525$$\gcd(2261,1275)=17.$$ 526Aside from some tedious arithmetic, that computation was systematic, 527and it was not necessary to factor any integers (which 528is something we do not know how to do quickly if the numbers 529involved have hundreds of digits). 530\begin{algorithm}{Greatest Common Division} 531\label{alg:gcd}\index{gcd algorithm} 532\index{compute!gcd} 533Given integers$a, b$, this algorithm computes$\gcd(a,b)$. 534\begin{steps} 535\item{} [Assume$a>b\geq 0$] We have 536$\gcd(a,b) = \gcd(|a|,|b|) = \gcd(|b|,|a|)$, 537so we may replace$a$and$b$by their absolute value and hence 538assume$a, b \geq 0$. If$a=b$output$a$and 539terminate. Swapping if necessary we assume$a>b$. 540\item{} [Quotient and Remainder] \label{alg:gcd_usediv} Using Algorithm~\ref{alg:division}, 541 write$a=bq+r$, with$0\leq r<b$and$q\in\Z$. 542\item{} [Finished?] If$r=0$then$b\mid a$, so we output$b$and terminate. 543\item{} [Shift and Repeat] \label{alg:gcd_shift} Set$a\la b$and$b \la r$, then go to 544step \ref{alg:gcd_usediv}. 545\end{steps} 546\end{algorithm} 547\begin{proof} 548Lemmas~\ref{lem:gcdprops}--\ref{lem:gcdprops2} 549imply that$\gcd(a,b) = \gcd(b,r)$so the gcd does not 550change in step \ref{alg:gcd_shift}. 551Since the remainders form a decreasing sequence of nonnegative 552integers, the algorithm terminates. 553\end{proof} 554See Section~\ref{sec:comp_gcd} for an implementation of 555Algorithm~\ref{alg:gcd}. 556 557\begin{example} 558Set$a=15$and$b=6$. 559\begin{eqnarray*} 560 15 &=& 6\cdot 2 + 3 \qquad\gcd(15,6)=\gcd(6,3)\\ 561 6 &=& 3\cdot 2 + 0 \qquad\gcd(6,3) =\gcd(3,0)=3 562\end{eqnarray*} 563\end{example} 564\noindent{}Note that 565we can just as easily do an example that is ten times 566as big, an observation that will be important in the 567proof of Theorem~\ref{thm:euclid} below. 568\begin{example}\label{ex:gcd10} 569Set$a=150$and$b=60$. 570\begin{eqnarray*} 571 150 &=& 60\cdot 2 + 30 \qquad\gcd(150,60)=\gcd(60,30)\\ 572 60 &=& 30\cdot 2 + 0 \qquad\,\,\,\gcd(60,30) =\gcd(30,0)=30 573\end{eqnarray*} 574\end{example} 575\begin{lemma}\label{lem:gcdmul} 576For any integers$a,b,n$, we have 577$$\gcd(an,bn) = \gcd(a,b)\cdot n.$$ 578\end{lemma} 579\begin{proof} 580 The idea is to follow Example~\ref{ex:gcd10}; we step through 581 Euclid's algorithm for$\gcd(an,bn)$and note that at every step the 582 equation is the equation from Euclid's algorithm for$\gcd(a,b)$but 583 multiplied through by~$n$. For simplicity, assume that both~$a$584 and~$b$are positive. We will prove the lemma by induction on 585$a+b$. The statement is true in the base case when$a+b=2$, 586 since then$a=b=1$. Now assume$a,b$are arbitrary with$a\leq b$. 587 Let~$q$and~$r$be such that$a = bq + r$and$0\leq r <b$. Then by 588 Lemmas~\ref{lem:gcdprops}--\ref{lem:gcdprops2}, we have$\gcd(a,b) =
589  \gcd(b,r)$. Multiplying$a=bq+r$by~$n$we see that$an = bnq +
590  rn$, so$\gcd(an,bn) = \gcd(bn,rn)$. Then 591 $$592 b+r = b + (a-bq)= a-b(q-1) \leq a < a+b, 593$$ 594 so by induction 595$\gcd(bn,rn) = \gcd(b,r)\cdot n$. Since$\gcd(a,b)=\gcd(b,r)$, 596 this proves the lemma. 597\end{proof} 598 599\begin{lemma}\label{lem:gcd2} 600 Suppose$a,b,n\in\Z$are such that$n\mid a$and$n\mid b$. Then 601$n\mid \gcd(a,b)$. 602\end{lemma} 603\begin{proof} 604Since$n\mid a$and$n\mid b$, there are integers 605$c_1$and$c_2$, such that$a=n c_1$and$b=n c_2$. 606By Lemma~\ref{lem:gcdmul}, 607$\gcd(a,b) = \gcd(n c_1, nc_2) = n\gcd(c_1, c_2)$, 608so$n$divides$\gcd(a,b)$. 609\end{proof} 610 611At this point it would be natural to formally analyze the complexity 612of Algorithm~\ref{alg:gcd}. We will not do this, because the main 613reason we introduced Algorithm~\ref{alg:gcd} is that it will allow us 614to prove Theorem~\ref{thm:fundamental}, and we have not chosen to 615formally analyze the complexity of the other algorithms in this book. 616For an extensive analysis of the complexity of 617Algorithm~\ref{alg:gcd}, see \cite[\S4.5.3]{knuth2}. 618 619With Algorithm~\ref{alg:gcd}, we can prove that if a prime divides the 620product of two numbers, then it has got to divide one of them. This 621result is the key to proving that prime factorization 622is unique. 623\begin{theorem}[Euclid]\label{thm:euclid}% 624\index{Euclid's theorem!on divisibility}% 625\ithm{Euclid} 626Let~$p$be a prime and$a, b\in \N$. 627If$p\mid ab$then$p\mid a$or$p\mid b$. 628\end{theorem} 629You might think this theorem is intuitively obvious'', but 630that might be 631because the fundamental theorem of arithmetic\index{fundamental 632 theorem of arithmetic} (Theorem~\ref{thm:fundamental}) is deeply 633ingrained in your intuition. Yet Theorem~\ref{thm:euclid} will be 634needed in our proof of the fundamental theorem of arithmetic. 635 636\begin{proof}[Proof of Theorem~\ref{thm:euclid}] 637 If$p\mid a$we are done. If$p\nmid a$then$\gcd(p,a)=1$, since 638 only~$1$and~$p$divide~$p$. By Lemma~\ref{lem:gcdmul}, 639$\gcd(pb,ab) = b$. Since$p\mid pb$and, by hypothesis,$p\mid ab$, 640 it follows from Lemma~\ref{lem:gcdmul} that 641 $$p\mid \gcd(pb,ab) = b.$$ 642\end{proof} 643 644\subsection{Numbers Factor as Products of Primes}\label{sec:numfact} 645\index{integers!factor} 646In this section, we prove that every natural number factors as a 647product of primes. 648Then we discuss the difficulty of finding such a decomposition 649in practice. We will wait until Section~\ref{sec:proof_fundamental} 650to prove that factorization is unique. 651 652As a first example, let$n=1275$. The sum of the digits 653of$n$is divisible by$3$, so$n$is divisible by$3$(see 654Proposition~\ref{prop:div3}), and we have$n=3\cdot 425$. 655The number$425$is divisible by$5$, since its last digit 656is$5$, and we have$1275 = 3\cdot 5 \cdot 85$. Again, 657dividing$85$by$5$, we have$1275 = 3\cdot 5^2 \cdot 17$, 658which is the prime factorization of$1275$. 659%Since$17\mid 1275$,~$n$is 660%definitely composite,$n=17 \cdot 75$. Next,$75$is$5\cdot
661%15=5\cdot 5\cdot 3$, and we find that$1275 = 3\cdot 5\cdot 5\cdot
662%17$. 663Generalizing this process proves the following proposition: 664\begin{proposition}\label{prop:numbers_factor}\iprop{prime factorization} 665Every natural number is a product of primes. 666\end{proposition} 667\begin{proof} 668Let~$n$be a natural number. If$n=1$, then~$n$is the empty 669product of primes. 670If$n$is prime, we are done. 671If$n$is composite, then$n=ab$with$a,b<n$. By induction,~$a$672and~$b$are products of primes, so~$n$is also a product of primes. 673\end{proof} 674 675Two questions immediately arise: (1) is this factorization unique, and 676(2) how quickly can we find such a factorization? Addressing (1), 677what if we had done something differently when breaking apart$1275$678as a product of primes? Could the primes that show up be different? 679Let's try: we have$1275 = 5\cdot 255$. Now$255=5\cdot 51$and 680$51=17\cdot 3$, and again the factorization is the same, as asserted 681by Theorem~\ref{thm:fundamental} above. We will prove uniqueness 682of the prime factorization of 683any integer in Section~\ref{sec:proof_fundamental}. 684 685Regarding (2), there are algorithms for integer factorization; e.g., in 686Sections~\ref{sec:ecm} and \ref{sec:alg_intfac} we will study and 687implement some of them. It is a major open problem to decide 688how fast integer factorization algorithms can be. 689\begin{openproblem}\index{open problem!fast integer factorization} 690\index{factorization!difficulty of} 691Is there an algorithm which can factor any 692integer~$n$in polynomial time? (See below 693for the meaning of polynomial time.) 694\end{openproblem} 695By \defn{polynomial time} we mean that there is a 696polynomial$f(x)$such that for any~$n$the number of steps needed by 697the algorithm to factor~$n$is less than$f(\log_{10}(n))$. Note 698that$\log_{10}(n)$is an approximation for the number of digits 699of the input~$n$to the algorithm. 700 701Peter Shor \cite{shor}\index{Shor} devised a polynomial time algorithm 702for factoring integers on quantum computers\index{quantum 703computer}\index{factorization!quantum}. We will not discuss his 704algorithm further, except to note that in 2001 IBM researchers 705built a quantum computer that used Shor's algorithm to factor$15$(see 706\cite{quantum15, ibm:shor15}). 707 708You can earn money by factoring certain large integers. Many 709cryptosystems would be easily broken if factoring certain large 710integers were easy. Since nobody has proven that factoring integers 711is difficult, one way to increase confidence that factoring is 712difficult is to offer cash prizes for factoring certain integers. For 713example, until recently there was a \$10000 bounty on factoring the
714following $174$-digit integer (see \cite{rsa:challenge}):
715$$716\begin{array}{l} 7171881988129206079638386972394616504398071635633794173827007\\ 7186335642298885971523466548531906060650474304531738801130339\\ 7196716199692321205734031879550656996221305168759307650257059 720\end{array} 721$$
722This number is known as RSA-576\index{RSA-576} since it has 576
723digits when written in binary (see Section~\ref{sec:compute_powers}
724for more on binary numbers).  It was factored at the German
725Federal Agency for Information Technology Security in December
7262003 (see \cite{factor576}):
727$$728\begin{array}{l} 729 398075086424064937397125500550386491199064362342526708406\\ 730 \hspace{1ex}385189575946388957261768583317\\ 731 \times\\ 732 472772146107435302536223071973048224632914695302097116459\\ 733 \hspace{1ex}852171130520711256363590397527 734 \end{array} 735$$
736The previous RSA challenge was the $155$-digit number
737$$738\begin{array}{l} 7391094173864157052742180970732204035761200373294544920599091\\ 7403842131476349984288934784717997257891267332497625752899781\\ 741833797076537244027146743531593354333897. 742\end{array}$$
743It was factored on 22 August 1999 by a group of sixteen researchers
744in four months on a cluster of 292 computers (see \cite{rsa155}).
745They found that RSA-155\index{RSA-155} is the product of the following two
746$78$-digit primes:
747\begin{align*}
748p &= 10263959282974110577205419657399167590071656780803806\\
749  &\hspace{4ex} 6803341933521790711307779\\
750q &= 10660348838016845482092722036001287867920795857598929\\
751  &\hspace{4ex} 1522270608237193062808643.
752\end{align*}
753The next RSA challenge is RSA-640:
754$$755\begin{array}{l} 75631074182404900437213507500358885679300373460228427275457201619\\ 75748823206440518081504556346829671723286782437916272838033415471\\ 75807310850191954852900733772482278352574238645401469173660247765\\ 7592346609, 760\end{array} 761$$
762and its factorization is worth \$20000. 763 764These RSA numbers were factored using an algorithm called the number 765field sieve (see \cite{lenstras:nfs}), which is the best-known general 766purpose factorization algorithm. A description of how the number 767field sieve works is beyond the scope of this book. However, the 768number field sieve makes extensive use of the elliptic curve 769factorization method, which we will describe in Section~\ref{sec:ecm}. 770 771\subsection{The Fundamental Theorem of Arithmetic}% 772\label{sec:proof_fundamental}\index{fundamental theorem of arithmetic} 773\index{integers!factor uniquely} 774We are ready to prove Theorem~\ref{thm:fundamental} 775using the following idea. 776Suppose we have two factorizations of~$n$. Using 777Theorem~\ref{thm:euclid} we cancel common primes from each factorization, 778one prime at a time. At the end, 779we discover that the factorizations must 780consist of exactly the same primes. The 781technical details are given below. 782\begin{proof} 783 If$n=1$, then the only factorization is the empty 784 product of primes, so suppose$n>1$. 785 786 By Proposition~\ref{prop:numbers_factor}, there exist primes 787$p_1,\ldots, p_d$such that 788$$789 n = p_1 p_2 \cdots p_d. 790$$ 791Suppose that 792$$n = q_1 q_2 \cdots q_m$$ 793is another expression of~$n$as a product of primes. 794Since 795$$p_1 \mid n = q_1 (q_2 \cdots q_m),$$ 796Euclid's theorem implies that$p_1 = q_1$or 797$p_1 \mid q_2\cdots q_m$. By induction, we see that$p_1 = q_i$for some~$i$. 798 799Now cancel$p_1$and$q_i$, and repeat the above argument. Eventually, 800we find that, up to order, the two factorizations are the same. 801\end{proof} 802 803 804 805\section{The Sequence of Prime Numbers} 806\label{sec:primeseq}\index{primes!sequence of} 807This section is concerned with three questions: 808\begin{enumerate} 809\item Are there infinitely many primes? 810\item Given$a,b\in\Z$, 811are there infinitely many primes of the form$ax+b$? 812\item How are the primes spaced along the number line? 813\end{enumerate} 814We first show that there are infinitely 815many primes, then state Dirichlet's theorem 816\index{theorem!of Dirichlet} that if$\gcd(a,b)=1$, 817then$ax+b$is a prime for infinitely many values of~$x$. Finally, we 818discuss the Prime Number Theorem\index{prime number theorem} 819which asserts that there are 820asymptotically$x/\log(x)$primes less than~$x, 821and we make a connection between this asymptotic formula 822and the Riemann Hypothesis\index{Riemann Hypothesis}. 823% For some other famous questions 824% about the sequence of primes, see Section~\ref{sec:primeassert}. 825 826\subsection{There Are Infinitely Many Primes}\label{sec:inf_primes} 827\index{primes!infinitely many} 828Each number on the left in the following table is prime. 829We will see soon that this pattern does not continue 830indefinitely, but something similar works. 831\begin{align*} 8323 &= 2+1\\ 8337 &= 2\cdot 3 + 1\\ 83431 &= 2\cdot 3 \cdot 5 + 1\\ 835211 &= 2\cdot 3 \cdot 5 \cdot 7 + 1\\ 8362311 &= 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 837\end{align*} 838 839\begin{theorem}[Euclid]\label{thm:euclid_primes} 840There are infinitely many primes.\ithm{infinitely many primes} 841\end{theorem} 842\begin{proof} 843Suppose thatp_1, p_2, \ldots, p_n$are~$n$distinct primes. 844We construct a prime$p_{n+1}$not equal to any of$p_1,\ldots, p_n$845as follows. If 846\begin{equation}\label{eqn:infprime} 847 N=p_1 p_2 p_3 \cdots p_n + 1, 848 \end{equation} 849then by Proposition~\ref{prop:numbers_factor} there is a factorization 850$$851 N = q_1 q_2 \cdots q_m 852$$ 853with each~$q_i$prime and$m\geq 1$. 854If$q_1 = p_i$for some~$i$, then$p_i\mid{}N$. 855Because of (\ref{eqn:infprime}), we also have 856$p_i\mid{}N-1$, so$p_i\mid{} 1=N-(N-1)$, which 857is a contradiction. 858Thus the prime$p_{n+1} = q_1$is not in the list$p_1,\ldots, p_n$, 859and we have constructed our new prime. 860\end{proof} 861 862For example, 863$$864 2\cdot 3 \cdot 5 \cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509. 865$$ 866Multiplying together the first~$6$primes and adding~$1$doesn't 867produce a prime, but it produces an integer that is merely 868divisible by a new prime. 869 870\begin{joke}[Hendrik Lenstra]\index{Lenstra}\index{joke} 871 There are infinitely many composite numbers. Proof. {\em To obtain 872 a new composite number, multiply together the first~$n$composite 873 numbers and don't add$1$.} 874\end{joke} 875 876 877 878\subsection{Enumerating Primes}\label{sec:enum_primes} 879The Sieve of Eratosthenes is an efficient way to enumerate all 880primes up to~$n$. The sieve works by first writing down all 881numbers up to$n$, noting that~$2$is prime, and crossing off all 882multiples of~$2$. Next, note that the first number not crossed off is~$3$, 883which is prime, and cross off all multiples of~$3$, etc. 884Repeating this process, we obtain a list of the primes up to~$n$. 885Formally, the algorithm is as follows: 886\begin{algorithm}{Sieve of Eratosthenes}\label{alg:sieve} 887Given a positive integer$n$, this algorithm computes a list of the 888primes up to$n$. 889\begin{steps} 890\item{}[Initialize] Let$X\assign [3,5,\ldots]$be the list 891of all odd integers between$3$and$n$. Let$P\assign [2]$be the list 892of primes found so far. 893\item{}[Finished?]\label{alg:sieve_2} 894Let$p$to be the first element of$X$. 895If$p\geq \sqrt{n}$, append each element of~$X$896to~$P$and terminate. Otherwise append$p$to$P$. 897\item{}[Cross Off] 898Set~$X$equal to the sublist of elements in~$X$that 899are not divisible by~$p$. 900Go to step \ref{alg:sieve_2}. 901\end{steps} 902\end{algorithm} 903For example, to list the primes$\leq 40$using the sieve, we 904proceed as follows. First$P=[2]$and 905$$X = [3,5,7,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39].$$ 906We append$3$to$P$and cross off all multiples of$3$to obtain 907the new list 908$$X = [5,7,11,13,17,19,23,25,29,31,35,37].$$ 909Next we append$5$to$P$, obtaining$P=[2,3,5]$, and cross off 910the multiples of$5$, to obtain$X = [7,11,13,17,19,23,29,31,37].$911Because$7^2\geq 40$, we append$X$to$P$and find that the 912primes less than$40$are 913$$914 2,3,5, 7,11,13,17,19,23,29,31,37. 915$$ 916\begin{proof}[Proof of Algorithm~\ref{alg:sieve}] 917The part of the algorithm that is not clear is that 918when the first element$a$of$X$satisfies$a\geq \sqrt{n}$, 919then each element of$X$is prime. 920To see this, suppose$m$is in$X$, so 921$\sqrt{n} \leq m\leq n$and that~$m$is divisible by 922no prime that is$\leq \sqrt{n}$. Write$m=\prod p_i^{e_i}$with 923the$p_i$distinct primes and$p_1<p_2<\ldots$. If$p_i>\sqrt{n}$924for each~$i$and there is more than one~$p_i$, then$m>n$, 925a contradiction. Thus some~$p_i$is less than$\sqrt{n}$, 926which also contradicts out assumptions on~$m$. 927\end{proof} 928See Section~\ref{sec:comp_enum_primes} for an implementation of 929Algorithm~\ref{alg:sieve}. 930 931 932\subsection{The Largest Known Prime}\index{primes!largest known} 933\index{largest known!prime} 934Though Theorem~\ref{thm:euclid_primes} implies that there are infinitely 935many primes, it still makes sense to ask the question 936What is the largest {\em known} prime?'' 937 938A \defn{Mersenne prime} is a prime of the form$2^q-1$. 939According to \cite{caldwell:largestprime} the largest known prime 940as of July 2004 is the Mersenne prime\index{primes!Mersenne} 941$$942 p = 2^{24036583}-1, 943$$ 944which has$7235733$decimal digits, so writing it out would fill 945over$10$books the size if this book. 946Euclid's theorem implies that there definitely is a prime bigger than 947this 7.2 million digit~$p$. Deciding whether or not a number 948is prime is interesting, both as a motivating problem and 949for applications to cryptography\index{cryptography}, as we will see in 950Section~\ref{sec:prob_prime_test} and Chapter~\ref{ch:crypto}. 951 952\subsection{Primes of the Form$ax+b$} 953\index{primes!of form$ax+b$} 954Next we turn to primes of the form$ax+b$, where~$a$and~$b$are 955fixed integers with$a>1$and~$x$varies over the natural numbers$\N$. 956We assume that$\gcd(a,b)=1$, because otherwise there is no 957hope that$ax+b$is prime infinitely often. 958For example,$2x+2=2(x+1)$is only prime if$x=0$, and is 959not prime for any other$x\in\N$. 960 961\begin{proposition}\index{primes!of form$4x-1$}\label{prop:4x-1} 962\iprop{infinitely many primes} 963There are infinitely many primes of the form$4x-1$. 964\end{proposition} 965Why might this be true? We list numbers of the form$4x-1$and underline 966those that are prime: 967$$\ul{3},\, \ul{7},\, \ul{11},\, 15,\, \ul{19},\, \ul{23},\, 27,\, \ul{31},\, 35,\, 39,\, 968 \ul{43},\, \ul{47},\, \ldots$$ 969It is plausible that underlined numbers would continue to appear 970indefinitely. 971 972\begin{proof} 973Suppose$p_1, p_2,\ldots, p_n$are distinct primes of the form$4x-1$. Consider 974the number 975$$976 N = 4p_1 p_2 \cdots p_n - 1. 977$$ 978Then$p_i \nmid N$for any~$i$. Moreover, not every prime$p\mid N$979is of the form$4x+1$; if they all were, then$N$would be of the form 980$4x+1$. Thus there is a$p\mid N$that is of the form$4x-1$. Since 981$p\not= p_i$for any~$i$, we have found a new prime of the form 982$4x-1$. We can repeat this process indefinitely, so the set of primes 983of the form$4x-1$cannot be finite. 984\end{proof} 985Note that this proof does not work if$4x-1$is replaced by$4x+1$, 986since a product of primes of the form$4x-1$can be of the form 987$4x+1$. 988 989 990\begin{example}\label{ex:inf_prime_form} 991Set$p_1=3$,$p_2=7$. Then 992$$993 N = 4\cdot 3 \cdot 7 - 1 = \ul{83} 994$$ 995is a prime of the form$4x-1$. Next 996$$997 N = 4\cdot 3 \cdot 7\cdot 83 - 1 = \ul{6971}, 998$$ 999which is again a prime of the form$4x-1$. 1000Again: 1001$$1002 N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 - 1 = 48601811 = 61 \cdot \ul{796751}. 1003$$ 1004This time$61$is a prime, but it is of the form$4x+1 = 4\cdot 15+1$. 1005However,$796751$is prime and 1006$796751 = 4\cdot 199188 - 1$. 1007We are unstoppable: 1008$$1009 N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 \cdot 796751 - 1 = \ul{5591}\cdot 6926049421. 1010$$ 1011This time the small prime,$5591$, is of the form$4x-1$and the large 1012one is of the form$4x+1$. 1013\end{example} 1014 1015\begin{theorem}[Dirichlet]\label{thm:dirichlet} 1016\ithm{Dirichlet} 1017Let~$a$and~$b$be integers with$\gcd(a,b)=1$. 1018Then there are infinitely many primes of the form 1019$ax+b$. 1020\end{theorem} 1021Proofs of this theorem typically use tools from advanced number 1022theory, and are beyond the scope of this book (see e.g., 1023\cite[\S VIII.4]{frohlichtaylor}). 1024 1025 1026\subsection{How Many Primes are There?}\index{primes!density of} 1027\index{density of primes} 1028We saw in Section~\ref{sec:inf_primes} 1029that there are infinitely many primes. 1030In order to get a sense for just how many primes there are, 1031we consider a few warm-up questions. 1032Then we consider some numerical evidence and state 1033the prime number theorem, which gives an asymptotic answer 1034to our question, and connect this theorem with a form 1035of the Riemann Hypothesis.\index{Riemann Hypothesis} 1036Our discussion of counting primes in this section is very cursory; 1037for more details, read Crandall and Pomerance's excellent 1038book \cite[\S1.1.5]{primenumbers}. 1039 1040The following vague discussion is meant to motivate a precise way to 1041measure the number of primes. How many natural numbers are even? 1042Answer: Half of them. How many natural numbers are of the form 1043$4x-1$? Answer: One fourth of them. How many natural numbers are 1044perfect squares? Answer: Zero percent of all natural numbers, in the 1045sense that the limit of the proportion of perfect squares to all 1046natural numbers converges to~$0$. More precisely, 1047$$1048 \lim_{x\ra \infty} 1049 \frac{\# \{n\in\N : 1050 n \leq x \text{ and n is a perfect square}\}}{x} = 0, 1051$$ 1052since the numerator is roughly$\sqrt{x}$and 1053$\lim_{x\ra\infty}\frac{\sqrt{x}}{x} = 0$. 1054Likewise, it is an easy consequence of Theorem~\ref{thm:primenumber} 1055below that zero percent of all natural numbers are prime 1056(see \exref{ch:primes}{ex:fewprimes}). 1057 1058We are thus led to ask another question: How many positive integers 1059$\leq x$are perfect squares? Answer: roughly$\sqrt{x}$. In the 1060context of primes, we ask, 1061\begin{question} 1062How many natural numbers$\leq x$are prime? 1063\end{question} 1064 1065Let 1066$$1067 \pi(x) = \#\{p\in \N : p \leq x \text{ is a prime}\}. 1068$$ 1069For example, 1070$$1071 \pi(6) =\#\{2,3,5\} = 3. 1072$$ 1073Some values of$\pi(x)$are given in Table~\ref{tab:primes}, 1074and Figures~\ref{fig:pix} and \ref{fig:pix2} contain graphs of$\pi(x)$. 1075These graphs look like straight lines, which maybe bend down slightly. 1076\begin{table}\index{table!values of$\pi(x)$} 1077\caption{Values of$\pi(x)$\label{tab:primes}}\vspace{1ex} 1078\begin{center} 1079\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline 1080$x$& 100 & 200 & 300 & 400 & 500 & 600 & 700 & 800 & 900 &1000\\\hline 1081$\pi(x)$& 25&46&62&78&95&109&125&139&154&168\\\hline 1082\end{tabular} 1083\end{center} 1084\end{table} 1085 1086\begin{figure} 1087\psset{unit=0.0042in} 1088\pspicture(-1,1)(1000,200) 1089%\psgrid[gridcolor=lightgray] 1090\psline[linewidth=0.03]{->}(-2,0)(1000,0)\rput(1015,0){$x$} 1091\psline[linewidth=0.03]{->}(0,-5)(0,200)\rput(0,215){$y$} 1092\pscircle*[linecolor=red](100,25){5}\rput(100,50){\mbox{\tiny$(100,25)$}} 1093\pscircle*[linecolor=red](200,46){5}\rput(200,70){\mbox{\tiny$(200,46)$}} 1094\pscircle*[linecolor=red](900,154){5}\rput(900,175){\mbox{\tiny$(900,154)$}} 1095\pscircle*[linecolor=red](1000,168){5}\rput(1005,180){\mbox{\tiny$(1000,168)$}} 1096\rput(-30,180){{\small$180$}} 1097\rput(-30,100){{\small$100$}} 1098\rput(900,-30){{\small$900$}} 1099\rput(100,-30){{\small$100$}} 1100\rput(200,150){Graph of$\pi(x)$} 1101\psline[linewidth=0.02](-5,180)(7,180) 1102\psline[linewidth=0.02](900,-5)(900,7) 1103\psline[linewidth=0.02](-5,100)(7,100) 1104\psline[linewidth=0.02](100,-5)(100,7) 1105\psline[linecolor=blue] 1106(10,4) 1107(20,8) 1108(30,10) 1109(40,12) 1110(50,15) 1111(60,17) 1112(70,19) 1113(80,22) 1114(90,24) 1115(100,25) 1116(110,29) 1117(120,30) 1118(130,31) 1119(140,34) 1120(150,35) 1121(160,37) 1122(170,39) 1123(180,41) 1124(190,42) 1125(200,46) 1126(210,46) 1127(220,47) 1128(230,50) 1129(240,52) 1130(250,53) 1131(260,55) 1132(270,57) 1133(280,59) 1134(290,61) 1135(300,62) 1136(310,63) 1137(320,66) 1138(330,66) 1139(340,68) 1140(350,70) 1141(360,72) 1142(370,73) 1143(380,75) 1144(390,77) 1145(400,78) 1146(410,80) 1147(420,81) 1148(430,82) 1149(440,85) 1150(450,87) 1151(460,88) 1152(470,91) 1153(480,92) 1154(490,93) 1155(500,95) 1156(510,97) 1157(520,97) 1158(530,99) 1159(540,99) 1160(550,101) 1161(560,102) 1162(570,104) 1163(580,106) 1164(590,107) 1165(600,109) 1166(610,111) 1167(620,114) 1168(630,114) 1169(640,115) 1170(650,118) 1171(660,120) 1172(670,121) 1173(680,123) 1174(690,124) 1175(700,125) 1176(710,127) 1177(720,128) 1178(730,129) 1179(740,131) 1180(750,132) 1181(760,134) 1182(770,136) 1183(780,137) 1184(790,138) 1185(800,139) 1186(810,140) 1187(820,141) 1188(830,145) 1189(840,146) 1190(850,146) 1191(860,149) 1192(870,150) 1193(880,151) 1194(890,154) 1195(900,154) 1196(910,155) 1197(920,157) 1198(930,158) 1199(940,159) 1200(950,161) 1201(960,162) 1202(970,163) 1203(980,165) 1204(990,166) 1205(1000,168) 1206\endpspicture 1207\caption{Graph of$\pi(x)$for$x<1000$}\label{fig:pix} 1208\end{figure} 1209 1210 1211Gauss\index{Gauss} had a lifelong love of enumerating primes. 1212Eventually he computed$\pi(3000000)$, though the author doesn't know 1213whether or not Gauss got the right answer, which is$216816$. Gauss 1214conjectured the following asymptotic formula for$\pi(x)$, which was 1215later proved independently by Hadamard\index{Hadamard} and Vall\'ee 1216Poussin\index{Vall\'ee Poussin} in 1896 (but will not be proved in 1217this book): 1218\begin{theorem}[Prime Number Theorem]\label{thm:primenumber} 1219\ithm{prime number} 1220The function$\pi(x)$is asymptotic to$x/\log(x)$, in the sense that 1221 $$\lim_{x\ra \infty} \frac{\pi(x)}{ x/\log(x)} = 1.$$ 1222\end{theorem} 1223We do nothing more here than motivate this deep theorem with 1224a few further numerical observations. 1225 1226The theorem implies that 1227$$\lim_{x\ra \infty} \pi(x)/x = \lim_{x\ra \infty} 1/\log(x)=0,$$ 1228so for any~$a$, 1229$$\lim_{x\ra\infty} \frac{\pi(x)}{x/(\log(x)-a)} = 1230 \lim_{x\ra\infty} \frac{\pi(x)}{x/\log(x)} - \frac{a\pi(x)}{x} 1231 = 1.$$ 1232Thus$x/(\log(x)-a)$is also asymptotic to$\pi(x)$for 1233any~$a$. See \cite[\S1.1.5]{primenumbers} for a discussion of why 1234$a=1$is the best choice. Table~\ref{tab:pnt} compares 1235$\pi(x)$and$x/(\log(x)-1)$for several$x<10000$. 1236 1237\begin{table}\index{table!comparing$\pi(x)$to$x/(\log(x)-1)$} 1238%? pi(x, c=0) = forprime(p=2,x,c++); c; 1239%? for(n=1,10,print(n*1000,"\t",pi(n*1000),"\t",n*1000/(log(n*1000)-1))) 1240\caption{Comparison of$\pi(x)$and$x/(\log(x)-1)$\label{tab:pnt}}\vspace{1ex} 1241 1242\begin{center} 1243\begin{tabular}{|l|l|l|}\hline 1244$\quad{}\!x$&$\pi(x)$&$x/(\log(x)-1)$(approx)\\\hline 12451000& 168& 169.2690290604408165186256278\\ 12462000& 303& 302.9888734545463878029800994\\ 12473000& 430& 428.1819317975237043747385740\\ 12484000& 550& 548.3922097278253264133400985\\ 12495000& 669& 665.1418784486502172369455815\\ 12506000& 783& 779.2698885854778626863677374\\ 12517000& 900& 891.3035657223339974352567759\\ 12528000& 1007& 1001.602962794770080754784281\\ 12539000& 1117& 1110.428422963188172310675011\\ 125410000& 1229& 1217.976301461550279200775705\\\hline 1255\end{tabular} 1256\end{center} 1257\end{table} 1258 1259\begin{figure} 1260\begin{center} 1261\vspace{2ex} 1262\input{graphics/pi_x_10000} 1263\vspace{4ex} 1264\input{graphics/pi_x_100000} 1265\caption{Graphs of$\pi(x)$for$x<10000$and$x<100000$\label{fig:pix2}} 1266\end{center} 1267\end{figure} 1268 1269As of 2004, the record for counting primes appears\index{largest known!value of$\pi(x)$} to be 1270$$1271 \pi(4\cdot 10^{22}) = 783964159847056303858. 1272$$ 1273 The computation of$\pi(4\cdot 10^{22})$reportedly took ten 1274 months on a 350 Mhz Pentium II (see \cite{pixproject} for more 1275 details). 1276 1277 For the reader familiar with complex analysis, we mention a 1278 connection between$\pi(x)$and the Riemann Hypothesis. The 1279 Riemann zeta function$\zeta(s)$is a complex analytic function on 1280$\C\setminus \{1\}$that extends the function defined on a right 1281 half plane by$\sum_{n=1}^{\infty} n^{-s}$. The Riemann 1282 Hypothesis\index{Riemann Hypothesis} is the conjecture that the 1283 zeros in$\C$of$\zeta(s)$with positive real part lie on the line 1284${\rm Re}(s)=1/2$. This conjecture is one of the Clay Math Institute 1285 million dollar millennium prize problems \cite{cmi}. 1286 1287 According to \cite[\S1.4.1]{primenumbers}, the Riemann Hypothesis is 1288 equivalent to the conjecture that 1289$$1290 \Li(x) = \int_{2}^{x} \frac{1}{\log(t)} dt 1291$$ 1292is a good'' approximation to$\pi(x)$, in the following 1293precise sense: 1294\begin{conjecture}[Equivalent to the Riemann Hypothesis] 1295\index{Riemann Hypothesis!bound on$\pi(x)$} 1296\mbox{}\newline{}For all$x\geq 2.01$, 1297$$1298 |\pi(x)-\Li(x)| \leq \sqrt{x}\log(x). 1299$$ 1300\end{conjecture} 1301If$x=2$, then$\pi(2)=1$and$\Li(2)=0$, 1302but$\sqrt{2}\log(2) = 0.9802\ldots$, so the inequality 1303is not true for$x\geq 2$, but$2.01$is big enough. 1304We will do nothing more to explain this conjecture, 1305and settle for one numerical example. 1306\begin{example} 1307Let$x=4\cdot 10^{22}. Then 1308\begin{align*} 1309 \pi(x) &= 783964159847056303858,\\ 1310 \Li(x) &= 783964159852157952242.7155276025801473\ldots, \\ 1311 |\pi(x) - \Li(x)| &= 5101648384.71552760258014\ldots, \\ 1312 \sqrt{x}\log(x) &= 10408633281397.77913344605\ldots, \\ 1313 x/(\log(x)-1) &= 783650443647303761503.5237113087392967\ldots. 1314\end{align*} 1315\end{example} 1316 1317 1318One of the best popular article on the prime number theorem and 1319the Riemann hypothesis is \cite{zagier:primes50}. 1320 1321\begin{exercises} 1322 1323\item Compute the greatest common divisor\gcd(455,1235)$by hand. 1324 1325\item\label{ex:handsieve} Use the Sieve of Eratosthenes 1326to make a list of all primes up to$100$. 1327 1328\item\label{ex:primesform} Prove that there are infinitely 1329many primes of the form$6x-1$.\index{primes!of the form$6x-1$} 1330 1331\item \label{ex:fewprimes} 1332Use Theorem~\ref{thm:primenumber} to deduce that 1333$\ds \lim_{x\to\infty} \frac{\pi(x)}{x} = 0$. 1334 1335\end{exercises} 1336 1337%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1338%% 1339%% Chapter: Integers Modulo n 1340%% 1341%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1342 1343\chapter{The Ring of Integers Modulo$n$}\label{ch:cong} 1344 1345This chapter is about the ring$\zmod{n}$of integers 1346modulo~$n$.\index{$\zmod{n}$} 1347First we discuss when linear equations modulo~$n$have a solution, 1348then introduce the Euler~$\vphi$function and prove Fermat's Little 1349Theorem and Wilson's theorem. Next we prove the Chinese Remainer 1350Theorem, which addresses simultaneous solubility of several linear 1351equations modulo coprime moduli. With these theoretical foundations 1352in place, in Section~\ref{sec:arith_mod_n} we introduce algorithms for 1353doing interesting computations modulo~$n$, including computing large 1354powers quickly, and solving linear equations. We finish with a very 1355brief discussion of finding prime numbers using arithmetic modulo~$n$. 1356 1357% We assume the reader has read Chapter~\ref{ch:primes}, and knows what 1358% it means to take the quotient of the ring$\Z$by an ideal$n\Z$. 1359 1360\section{Congruences Modulo$n$}\index{congruences} 1361\index{equivalence relation!congruence modulo~$n$} 1362\index{integers!modulo~$n$} 1363\label{sec:congruences} 1364In this section we define the ring$\zmod{n}$of integers modulo~$n$, 1365introduce the Euler$\vphi$-function,\index{Euler!phi function} 1366\index{phi@$\vphi$function} and relate it to the 1367multiplicative order\index{multiplicative!order} 1368of certain elements of$\zmod{n}$. 1369 1370If$a,b\in\Z$and$n\in\N$, we say that$a$is {\em congruent 1371 to~$b$modulo~$n$} if$n\mid a-b$, and write$a\con b\pmod{n}$. 1372Let$n\Z=(n)$be the ideal of$\Z$generated by~$n$. 1373\begin{definition}[Integers Modulo$n$] 1374The \defn{ring of integers modulo~$n$} 1375is the quotient ring$\zmod{n}$of equivalence classes of integers 1376modulo~$n$. It is equipped with its natural ring structure: 1377$$1378 (a + n\Z) + (b + n\Z) = (a+b) + n\Z 1379$$ 1380$$1381 (a + n\Z) \cdot (b + n\Z) = (a\cdot b) + n\Z. 1382$$ 1383\end{definition} 1384 1385 1386\begin{example} 1387For example, 1388$$1389 \zmod{3} = \{ \{\ldots, -3, 0, 3, \ldots\}, 1390 \{\ldots, -2, 1, 4, \ldots\}, 1391 \{\ldots, -1, 2, 5, \ldots\}\} 1392$$ 1393\end{example} 1394 1395\label{page:znring} 1396We use the notation$\zmod{n}$because$\zmod{n}$is the quotient of 1397the ring~$\Z$by the ideal$n\Z$of multiples of~$n$. Because 1398$\zmod{n}$is the quotient of a ring by an ideal, the ring structure 1399on~$\Z$induces a ring structure on$\zmod{n}$. We often let~$a$1400or$a\pmod{n}$1401denote the equivalence class$a+n\Z$of~$a$. If~$p$is a prime, then 1402$\zmod{p}$is a field\index{field!of integers modulo$p$} (see 1403\exref{ch:cong}{ex:zpfield}).\index{finite field} 1404 1405We call the natural reduction map$\Z \to \zmod{n}$, which sends$a$to 1406$a+n\Z$, \defn{reduction modulo~$n$}. We also say that$a$is a 1407\defn{lift} of$a+n\Z$. Thus, e.g.,$7$is a lift of$1$mod$3$, 1408since$7+3\Z = 1+3\Z$. 1409 1410We can use that arithmetic in$\zmod{n}$is well defined is to 1411derive tests for divisibility\index{divisibility tests} by$n$(see 1412\exref{ch:cong}{ex:divrules}). 1413\begin{proposition}\label{prop:div3}\iprop{divisibility by 3} 1414A number$n\in\Z$is divisible by~$3$if and only if 1415the sum of the digits of~$n$is divisible by~$3$. 1416\end{proposition} 1417\begin{proof} 1418Write 1419 $$n=a+10b+100c+\cdots,$$ 1420where the digits of~$n$are$a$,$b$,$c$, etc. 1421Since$10\con 1\pmod{3}$, 1422$$1423 n = a + 10b + 100c+\cdots \con a + b + c+\cdots \pmod{3}, 1424$$ 1425from which the proposition follows. 1426\end{proof} 1427 1428 1429\subsection{Linear Equations Modulo~$n$}\label{sec:lineq}\index{linear equations modulo$n$}% 1430\index{modular arithmetic!and linear equations} In this section, we 1431are concerned with how to decide whether or not a linear equation of 1432the form$ax\con b \pmod{n}$has a solution modulo~$n$. 1433Algorithms for {\em computing} solutions to$ax\con
1434b\pmod{n}$are the topic of Section~\ref{sec:arith_mod_n}. 1435 1436First we prove a proposition that gives a criterion under 1437which one can cancel a quantity from both sides of a congruence. 1438\begin{proposition}[Cancellation]\label{prop:cancel}\iprop{cancellation} 1439If$\gcd(c,n)=1$and 1440$$1441 ac\con bc\pmod{n}, 1442$$ 1443then$a \con b\pmod{n}$. 1444\end{proposition} 1445\begin{proof} 1446By definition 1447$$1448 n \mid ac - bc = (a-b)c. 1449$$ 1450Since$\gcd(n,c)=1$, it follows 1451from Theorem~\ref{thm:fundamental} that$n\mid a-b$, so 1452$$1453 a \con b\pmod{n}, 1454$$ 1455as claimed. 1456\end{proof} 1457 1458 1459 1460When~$a$has a multiplicative inverse$a'$in$\zmod{n}$(i.e., 1461$aa'\con 1\pmod{n}$) then the equation$ax\con b\pmod{n}$has a unique 1462solution$x\con a'b\pmod{n}$modulo~$n$. Thus, it is of interest to 1463determine the units in$\zmod{n}$, i.e., the elements which have a 1464multiplicative inverse. 1465 1466We will use complete sets of residues\index{complete set of residues} 1467to prove that the units in$\zmod{n}$are exactly the~$a\in\zmod{n}$1468such that$\gcd(\tilde{a},n)=1$for any lift$\tilde{a}$of~$a$1469to~$\Z$(it doesn't matter which lift). 1470 1471\begin{definition}[Complete Set of Residues] 1472We call a subset$R\subset\Z$of size~$n$whose reductions modulo~$n$are 1473pairwise distinct a \defn{complete set of residues} 1474modulo~$n$. In other words, a complete set of residues is a choice of 1475representative for each equivalence class in$\zmod{n}$. 1476\end{definition} 1477For example, 1478$$1479 R=\{0,1,2,\ldots,n-1\} 1480$$ 1481is a complete set of residues modulo~$n$. 1482When$n=5$, 1483$R = \{0,1,-1,2,-2\}$1484is a complete set of residues. 1485 1486\begin{lemma}\label{lem:residues} 1487If~$R$is a complete set of residues modulo~$n$and$a\in\Z$with 1488$\gcd(a,n)=1$, then$aR = \{ax : x \in R\}$1489is also a complete set of residues modulo~$n$. 1490\end{lemma} 1491\begin{proof} 1492If$ax\con ax'\pmod{n}$with$x, x'\in R$, then 1493Proposition~\ref{prop:cancel} implies that$x\con{}x'\pmod{n}$. 1494Because$R$is a complete set of residues, this implies 1495that$x=x'$. Thus the elements of 1496$aR$have distinct reductions modulo~$n$. 1497It follows, since$\#aR=n$, that$aR$is a 1498complete set of residues modulo~$n$. 1499\end{proof} 1500 1501\begin{proposition}[Units]\label{prop:unitsmodn}\iprop{units} 1502If$\gcd(a,n)=1$, then the equation 1503$
1504 ax\con b\pmod{n}
1505$1506has a solution, and that solution is unique modulo~$n$. 1507\end{proposition} 1508\begin{proof} 1509Let~$R$be a complete set of residues modulo~$n$, so there 1510is a unique element of~$R$that is congruent to~$b$modulo~$n$. 1511By Lemma~\ref{lem:residues}, 1512$aR$is also a complete set of residues modulo~$n$, so 1513there is a unique element$ax\in aR$that is congruent 1514to~$b$modulo~$n$, and we have$ax\con b\pmod{n}$. 1515\end{proof} 1516Algebraically, this proposition asserts that if$\gcd(a,n)=1$, then 1517the map$\zmod{n}\ra \zmod{n}$given by left multiplication by~$a$is 1518a bijection. 1519 1520\begin{example} 1521Consider the equation$2x\con 3\pmod{7}$, 1522and the complete set$R = \{0,1,2,3,4,5,6\}$1523of coset representatives. We have 1524$$1525 2R = \{0,2,4,6,8\con 1, 10\con 3, 12\con 5\}, 1526$$ 1527so$2\cdot 5\con 3\pmod{7}$. 1528\end{example} 1529 1530When$\gcd(a,n)\neq 1$, then the equation$ax\con b\pmod{n}$may or 1531may not have a solution. For example,$2x\con 1\pmod{4}$has no 1532solution, but$2x\con 2\pmod{4}$does, and in fact it has more than 1533one mod~$4$($x=1$and$x=3$). Generalizing 1534Proposition~\ref{prop:unitsmodn}, we obtain the following more general 1535criterion for solvability. 1536\begin{proposition}[Solvability]\label{prop:cancel2}\iprop{solvability} 1537The equation$ax\con b\pmod{n}$has a solution 1538if and only if$\gcd(a,n)$divides~$b$. 1539\end{proposition} 1540\begin{proof} 1541 Let$g=\gcd(a,n)$. If there is a solution~$x$to the equation 1542$ax\con b\pmod{n}$, then$n\mid (ax-b)$. Since$g\mid n$and$g\mid
1543  a$, it follows that$g\mid b$. 1544 1545 Conversely, suppose that$g\mid b$. Then$n\mid (ax-b)$if and only 1546 if $$1547 \frac{n}{g} \mid \left(\frac{a}{g} x - \frac{b}{g}\right).$$ 1548 Thus$ax\con b\pmod{n}$has a solution if and only if$\frac{a}{g}x
1549  \con \frac{b}{g}\pmod{\frac{n}{g}}$has a solution. Since 1550$\gcd(a/g, n/g)=1$, Proposition~\ref{prop:unitsmodn} implies this 1551 latter equation does have a solution. 1552\end{proof} 1553 1554In Chapter~\ref{ch:reciprocity} we will study quadratic reciprocity, 1555which gives a nice criterion for whether or not a quadratic equation 1556modulo~$n$has a solution. 1557 1558\subsection{Fermat's Little Theorem} 1559\index{Fermat's little theorem}% 1560\label{sec:flittle}% 1561\index{theorem!Fermat's little}% 1562The group of units$(\zmod{n})^*$of the ring$\zmod{n}$will 1563be of great interest to us. Each element of 1564this group has an order, and Lagrange's theorem from group theory 1565implies that each element of$(\zmod{n})^*$has order that divides 1566the order of$(\zmod{n})^*$. In elementary number theory this 1567fact goes by the monicker Fermat's Little Theorem'', and we 1568reprove it from basic principles in this section. 1569 1570\begin{definition}[Order of an Element]\index{order!of element}% 1571\index{modular arithmetic!order of element}\label{defn:order} 1572Let$n\in\N$and$x\in\Z$and suppose that$\gcd(x,n)=1$. 1573The \defn{order} of$x$modulo~$n$is the smallest$m\in\N$1574such that 1575$$1576 x^m \con 1\pmod{n}. 1577$$ 1578\end{definition} 1579To show that the definition makes sense, we verify 1580that such an~$m$exists. Consider$x, x^2, x^3, \ldots$modulo~$n$. 1581There are only finitely many residue classes modulo~$n$, so we must 1582eventually find two integers$i, j$with$i<j$such that 1583$$1584 x^j\con x^i\pmod{n}. 1585$$ 1586Since$\gcd(x,n)=1$, Proposition~\ref{prop:cancel} implies that 1587we can cancel~$x$'s and conclude that 1588$$1589 x^{j-i}\con 1\pmod{n}. 1590$$ 1591 1592 1593\begin{definition}[Euler's phi-function]\label{def:phi}\index{Euler!phi function} 1594For$n\in\N, let 1595$$1596 \vphi(n) = \#\{a \in \N : a \leq n \text{ and } \gcd(a,n)=1\}. 1597$$ 1598\end{definition} 1599For example, 1600\begin{align*} 1601 \vphi(1) &= \#\{1\} = 1,\\ 1602 \vphi(2) &= \#\{1\} = 1,\\ 1603 \vphi(5) &= \#\{1,2,3,4\} = 4,\\ 1604 \vphi(12) &= \#\{1,5,7,11\} = 4.\\ 1605\end{align*} 1606Also, if~p$is any prime number then 1607$$1608 \vphi(p) = \#\{1,2,\ldots,p-1\} = p-1. 1609$$ 1610In Section~\ref{sec:multi_funcs}, we will prove that~$\vphi$is a 1611multiplicative function. This will yield an easy way to compute 1612$\vphi(n)$in terms of the prime factorization of~$n$. 1613 1614\begin{theorem}[Fermat's Little Theorem]\label{thm:fermatlittle} 1615\ithm{Fermat's little} 1616If$\gcd(x,n)=1$, then 1617$$1618 x^{\vphi(n)} \con 1\pmod{n}. 1619$$ 1620\end{theorem} 1621\begin{proof} 1622As mentioned above, Fermat's Little Theorem has the following group-theoretic 1623\index{Fermat's little theorem!group-theoretic interpretation} 1624interpretation. The set of units in$\zmod{n}$is a group 1625\index{group!$(\zmod{m})^*$} 1626$$1627(\zmod{n})^* 1628= \{ a \in \zmod{n} : \gcd(a,n) = 1\}. 1629$$ 1630which has order~$\vphi(n)$. The theorem then asserts 1631that the order of an element of$(\zmod{n})^*$divides the order 1632$\vphi(n)$of$(\zmod{n})^*$. This is a special case of the more 1633general fact (Lagrange's theorem) that if~$G$is a finite group and 1634$g\in G$, then the order of~$g$divides the cardinality of~$G$. 1635 1636We now give an elementary proof of the theorem. Let 1637$$1638 P = \{ a : 1\leq a \leq n \text{ and } \gcd(a,n) = 1\}. 1639$$ 1640In the same way that we proved Lemma~\ref{lem:residues}, 1641we see that the reductions modulo~$n$of the elements of$xP$1642are the same as the reductions of the elements of$P$. 1643Thus 1644$$1645 \prod_{a\in P} (xa) \con \prod_{a \in P} a \pmod{n}, 1646$$ 1647since the products are over the same numbers modulo~$n$. 1648Now cancel the$a$'s on both sides to get 1649$$x^{\#P} \con 1\pmod{n},$$ 1650as claimed. 1651\end{proof} 1652 1653 1654 1655\subsection{Wilson's Theorem}\index{Wilson's theorem}\index{theorem!of Wilson} 1656The following characterization of prime numbers, from the 1770s, is 1657called Wilson's Theorem'', though it was first proved by 1658Lagrange\index{Lagrange}. 1659\begin{proposition}[Wilson's Theorem]\label{prop:wilson}\iprop{Wilson} 1660An integer$p>1$is prime if and only if 1661$(p-1)! \con -1 \pmod{p}.$1662\end{proposition} 1663For example, 1664if$p=3$, then$(p-1)! = 2\con -1\pmod{3}$. 1665If$p=17$, then 1666$$(p-1)! = 20922789888000 \con -1\pmod{17}.$$ 1667But if$p=15$, then 1668$$(p-1)! = 87178291200 \con 0 \pmod{15},$$ 1669so$15$is composite. Thus Wilson's theorem could be viewed 1670as a primality test, though, from a computational point of view, 1671it is probably the {\em least efficient} 1672primality test since computing$(n-1)!$takes so many steps. 1673\begin{proof} 1674The statement is clear when$p=2$, so henceforth we assume 1675that$p>2$. 1676We first assume that~$p$is prime and prove that 1677$(p-1)! \con -1\pmod{p}$. If$a\in\{1,2,\ldots,p-1\}$then 1678the equation 1679$$1680 ax\con 1\pmod{p} 1681$$ 1682has a unique solution$a'\in\{1,2,\ldots,p-1\}$. 1683If$a=a'$, then$a^2\con 1\pmod{p}$, so 1684$p\mid a^2-1 = (a-1)(a+1)$, so 1685$p\mid (a-1)$or$p\mid (a+1)$, so$a\in\{1,p-1\}$. 1686We can thus pair off the elements of 1687$\{2,3,\ldots,p-2\}$, 1688each with their inverse. 1689Thus 1690$$1691 2\cdot 3 \cdot \cdots \cdot (p-2) \con 1\pmod{p}. 1692$$ 1693Multiplying both sides by$p-1$proves that 1694$(p-1)! \con -1\pmod{p}$. 1695 1696Next we assume that$(p-1)! \con -1\pmod{p}$and 1697prove that~$p$must be prime. Suppose not, so that~$p\geq 4$1698is a composite number. Let~$\ell$be a prime divisor 1699of~$p$. Then$\ell<p$, so$\ell\mid (p-1)!$. Also, 1700by assumption, 1701$$1702 \ell \mid p \mid ((p-1)! + 1). 1703$$ 1704This is a contradiction, because a prime can not divide a number~$a$and 1705also divide$a+1$, since it would then have to divide$(a+1) - a=1$. 1706\end{proof} 1707 1708\begin{example} 1709We illustrate the key step in the above proof in the case$p=17$. 1710We have 1711$$17122\cdot 3 \cdots 15 1713 = (2\cdot 9)\cdot(3\cdot 6)\cdot(4\cdot 13)\cdot 1714 (5\cdot 7)\cdot(8\cdot 15)\cdot(10\cdot 12)\cdot(14\cdot 11) 1715 \con 1\pmod{17},$$ 1716where we have paired up the numbers$a, b$for 1717which$ab\con 1\pmod{17}. 1718\end{example} 1719 1720\section{The Chinese Remainder Theorem}\label{sec:chinese}% 1721\index{Chinese remainder theorem} 1722In this section we prove the Chinese Remainder Theorem, which gives 1723conditions under which a system of linear equations is guaranteed to 1724have a solution. 1725In the 4th century a Chinese mathematician asked the following: 1726\begin{question}\label{q:chinese} 1727There is a quantity whose number is unknown. Repeatedly divided 1728by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the 1729remainder is 2. What is the quantity? 1730\end{question} 1731In modern notation, Question~\ref{q:chinese} asks us to 1732find a positive integer solution to the following system of 1733three equations: 1734\begin{align*} 1735x &\con 2 \pmod{3}\\ 1736x &\con 3 \pmod{5}\\ 1737x &\con 2 \pmod{7} 1738\end{align*} 1739The Chinese Remainder Theorem asserts that a solution 1740exists, and the proof gives a method to find one. 1741(See Section~\ref{sec:arith_mod_n} for the necessary algorithms.) 1742 1743 1744\begin{theorem}[Chinese Remainder Theorem]\label{thm:crt}% 1745\ithm{Chinese remainder} 1746Leta, b\in\Z$and$n,m\in\N$such that 1747$\gcd(n,m)=1$. Then there exists$x\in\Zsuch that 1748\begin{align*} 1749x&\con a\pmod{m},\\ 1750x&\con b\pmod{n}. 1751\end{align*} 1752Moreover~x$is unique modulo~$mn$. 1753\end{theorem} 1754\begin{proof} 1755If we can solve for~$t$in the equation 1756$$1757 a+tm \con b \pmod{n}, 1758$$ 1759then$x=a+tm$will satisfy both congruences. 1760To see that we can solve, subtract~$a$from 1761both sides and use Proposition~\ref{prop:unitsmodn} 1762together with our assumption that$\gcd(n,m)=1$to see that 1763there is a solution. 1764 1765For uniqueness, suppose that$x$and$y$solve both congruences. Then 1766$z=x-y$satisfies$z\con 0\pmod{m}$and$z\con 0\pmod{n}$, so$m\mid
1767z$and$n\mid z$. Since$\gcd(n,m)=1$, it follows that$nm\mid z$, so 1768$x\con y\pmod{nm}$. 1769\end{proof} 1770 1771% An alternative approach to proving Theorem~\ref{thm:crt} is to prove 1772% the result for the special cases$a=1,b=0$and for$a=0,b=1$, then 1773% take a suitable linear combination of those two solutions. This is 1774% geometrically appealing, since it is like writing a vector in terms of 1775% a basis. 1776 1777\begin{algorithm}{Chinese Remainder Theorem}\label{alg:crt} 1778Given coprime integers$m$and$n$and integers$a$and$b$, 1779this algorithm find an integer$x$such that$x\con a\pmod{m}$1780and$x\con b\pmod{n}$. 1781\begin{steps} 1782\item{}[Extended GCD] Use Algorithm~\ref{alg:xgcd} below 1783to find integers$c,d$such that$cm+dn=1$. 1784\item{}[Answer] Output$x =a + (b-a)cm$and terminate. 1785\end{steps} 1786\end{algorithm} 1787\begin{proof} 1788Since$c\in\Z$, we have$x\con a\pmod{m}$, 1789and using that$cm+dn=1$, we have 1790$a + (b-a)cm \con a + (b-a) \con b\pmod{n}. 1791\end{proof} 1792 1793Now we can answer Question~\ref{q:chinese}. 1794First, we use Theorem~\ref{thm:crt} 1795to find a solution to the pair of equations 1796\begin{align*} 1797x &\con 2 \pmod{3},\\ 1798x &\con 3 \pmod{5}. 1799\end{align*} 1800Seta=2$,$b=3$,$m=3$,$n=5$. 1801Step 1 is to find a solution to$t\cdot 3 \con 3-2\pmod{5}$. 1802A solution is$t=2$. Then$x=a+tm=2+2\cdot 3 = 8$. 1803Since any~$x'$with$x'\con x\pmod{15}is also a solution to 1804those two equations, we can solve all three equations by 1805finding a solution to the pair of equations 1806\begin{align*} 1807x &\con 8 \pmod{15}\\ 1808x &\con 2 \pmod{7}. 1809\end{align*} 1810Again, we find a solution tot\cdot 15 \con 2-8\pmod{7}$. 1811A solution is$t = 1$, so 1812$$x=a+tm=8+15=23.$$ 1813Note that there are other solutions. Any$x'\con x\pmod{3\cdot 5\cdot 7}$1814is also a solution; e.g.,$23+3\cdot 5\cdot 7 = 128$. 1815 1816\subsection{Multiplicative Functions}\index{multiplicative!functions}% 1817\label{sec:multi_funcs}% 1818\begin{definition}[Multiplicative Function] 1819A function$f:\N\ra \Z$is 1820\defn{multiplicative} if, whenever$m, n\in\N$and$\gcd(m,n)=1$, we have 1821$$1822 f(mn) = f(m)\cdot f(n). 1823$$ 1824\end{definition} 1825Recall from Definition~\ref{def:phi} 1826that the \defn{Euler$\vphi$-function}\index{Euler!phi function} is 1827$$1828 \vphi(n) = \#\{a : 1\leq a \leq n\text{ and }\gcd(a,n)=1\}. 1829$$ 1830 1831\begin{lemma}\label{lem:units_map} 1832Suppose that$m,n\in\N$and$\gcd(m,n)=1$. 1833Then the map 1834\begin{equation}\label{eqn:crtprod} 1835\psi: (\zmod{mn})^* \ra (\zmod{m})^* \cross (\zmod{n})^*. 1836\end{equation} 1837defined by 1838$$1839 \psi(c) = (c\text{ mod } m, \,\,c \text{ mod }n) 1840$$ 1841is a bijection. 1842\end{lemma} 1843\begin{proof} 1844We first show that~$\psi$is injective. If$\psi(c)=\psi(c')$, then 1845$m\mid c-c'$and$n\mid c-c'$, so$nm\mid c-c'$because$\gcd(n,m)=1$. 1846Thus$c=c'$as elements of$(\zmod{mn})^*$. 1847 1848Next we show that~$\psi$is surjective. Given~$a$and~$b$1849with$\gcd(a,m)=1$and 1850$\gcd(b,n)=1$, Theorem~\ref{thm:crt} implies that there 1851exists~$c$with$c\con a\pmod{m}$and$c\con b\pmod{n}$. We 1852may assume that$1\leq c\leq nm$, and since$\gcd(a,m)=1$and 1853$\gcd(b,n)=1$, we must have$\gcd(c,nm)=1$. Thus$\psi(c)=(a,b)$. 1854\end{proof} 1855 1856\begin{proposition}[Multiplicativity of$\vphi$]\label{prop:phimult}\iprop{multiplicative of Euler's function} 1857The function$\vphi$is multiplicative. 1858\index{phi function!is multiplicative}\index{Euler!phi function!is multiplicative} 1859\end{proposition} 1860\begin{proof} 1861 The map~$\psi$of Lemma~\ref{lem:units_map} is a bijection, so the 1862 set on the left in (\ref{eqn:crtprod}) has the same size as the 1863 product set on the right in (\ref{eqn:crtprod}). Thus 1864 $$1865 \vphi(mn) = \vphi(m)\cdot \vphi(n). 1866$$ 1867\end{proof} 1868% See \exref{ch:cong}{ex:multproof2} for an alternative proof of 1869% Proposition~\ref{prop:phimult} that uses the natural isomorphism 1870%$\zmod{mn} \ra \zmod{m} \cross \zmod{n}$. 1871 1872 1873The proposition is helpful in computing$\vphi(n)$, at least 1874if we assume we can compute the factorization of~$n$(see 1875Section~\ref{sec:phin} for a connection between factoring$n$1876and computing$\vphi(n)$). 1877For example, 1878$$1879 \vphi(12) = \vphi(2^2)\cdot \vphi(3) = 2\cdot 2 = 4. 1880$$ 1881Also, for$n\geq 1$, we have 1882\begin{equation}\label{eqn:phipower} 1883 \vphi(p^n) = p^n - \frac{p^n}{p} = p^n - p^{n-1} = p^{n-1}(p-1), 1884 \end{equation} 1885 since$\vphi(p^n)$is the number of numbers less than$p^n$1886minus the number of those that are divisible by$p$. 1887Thus, e.g., 1888$$1889 \vphi(389\cdot 11^2) = 388 \cdot (11^2 - 11) = 388\cdot 110 = 42680. 1890$$ 1891 1892\section{Quickly Computing Inverses and Huge Powers}\index{compute!inverse modulo$n$}\index{compute!powers modulo$n$} 1893\label{sec:arith_mod_n} 1894This section is about how to solve the equation$ax\con 1\pmod{n}$1895when we know it has a solution, and how to efficiently compute 1896$a^m\pmod{n}$. We also discuss a simple probabilistic primality 1897test\index{primality test!probabilistic} that relies on our ability to 1898compute$a^m\pmod{n}$quickly. All three of these algorithms are of 1899fundamental importance to the cryptography algorithms of 1900Chapter~\ref{ch:crypto}. 1901 1902 1903\subsection{How to Solve$ax\con 1\pmod{n}$} 1904Suppose$a, n\in\N$with$\gcd(a,n)=1$. Then 1905by Proposition~\ref{prop:unitsmodn} 1906the equation$ax\con 1\pmod{n}$has a unique solution. 1907How can we find it? 1908 1909\begin{proposition}[Extended Euclidean representation] 1910\label{prop:xgcd}\iprop{extended Euclidean} 1911Suppose$a,b\in\Z$and let$g=\gcd(a,b)$. Then 1912there exists$x,y\in\Z$such that 1913$$1914 ax + by = g. 1915$$ 1916\end{proposition} 1917\begin{remark} 1918If$e=cg$is a multiple of~$g$, then 1919$cax + cby = cg = e,$so$e = (cx)a+(cy)b$can 1920also be written in terms of~$a$and~$b$. 1921\end{remark} 1922 1923\begin{proof}[Proof of Proposition~\ref{prop:xgcd}] 1924 Let$g=\gcd(a,b)$. Then 1925$\gcd(a/d,b/d)=1$, so by Proposition~\ref{prop:cancel2} the equation 1926\begin{equation}\label{eqn:xgcd} 1927\frac{a}{g}\cdot x\con 1\left({\rm mod} \hspace{1ex}\frac{b}{g}\right) 1928\end{equation} 1929has a solution$x\in\Z$. Multiplying (\ref{eqn:xgcd}) through by~$g$1930yields$ax \con g \pmod{b}$, so there exists~$y$such that 1931$b\cdot (-y) = ax-g$. Then$ax+by = g$, as required. 1932\end{proof} 1933 1934Given$a,b$and$g=\gcd(a,b)$, our proof of 1935Proposition~\ref{prop:xgcd} gives a way to explicitly find$x,y$such 1936that$ax+by=g$, assuming one knows an algorithm to solve linear 1937equations modulo~$n$. Since we do not know such an algorithm, we now 1938discuss a way to explicitly find~$x$and~$y$. This algorithm 1939will in fact enable us to solve linear equations modulo$n$---to solve 1940$ax\con 1\pmod{n}$when$\gcd(a,n)=1$, use the algorithm below to 1941find~$x$and~$y$such that$ax+ny = 1$. Then$ax\con 1\pmod{n}.$1942 1943Suppose$a=5$and$b=7$. The steps of Algorithm~\ref{alg:gcd} to 1944compute$\gcd(5,7)$are, as follows. Here we underlying, because it 1945clarifies the subsequent back substitution we will use to find~$x$1946and~$y. 1947\begin{align*} 1948 \ul{7}&=1\cdot \ul{5} + \underline{2} & \text{so } \ul{2} &= \ul{7} - \ul{5}\hfill\\ 1949 \ul{5}&=2\cdot \ul{2} + \ul{1} & \text{so } \ul{1}&= \ul{5} - 2\cdot \ul{2} = \ul{5} - 2(\ul{7}-\ul{5}) = 3\cdot\ul{5}-2\cdot\ul{7}\hfill 1950\end{align*} 1951On the right, we have back-substituted in order to write each partial 1952remainder as a linear combination of~a$and~$b$. In the last step, 1953we obtain$\gcd(a,b)$as a linear combination of~$a$and~$b$, as 1954desired. 1955 1956That example was not too complicated, so we try another one. 1957Let$a=130$and$b=61. We have 1958\begin{align*} 1959\ul{130} &= 2\cdot \ul{61} + \ul{8} & \ul{8} &= \ul{130}-2\cdot\ul{61}\\ 1960 \ul{61} &= 7\cdot \ul{8} + \ul{5} & \ul{5} &= -7\cdot\ul{130}+15\cdot\ul{61}\\ 1961 \ul{8} &= 1\cdot \ul{5} + \ul{3} & \ul{3} &= 8\cdot\ul{130}-17\cdot\ul{61}\\ 1962 \ul{5} &= 1\cdot \ul{3} + \ul{2} & \ul{2} &=-15\cdot\ul{130}+32\cdot\ul{61}\\ 1963 \ul{3} &= 1\cdot \ul{2} + \ul{1}& \ul{1} &= 23\cdot\ul{130}-49\cdot\ul{61} 1964\end{align*} 1965Thusx=23$and$y=-49$is a solution to$130 x + 61 y = 1$. 1966 1967\begin{algorithm}{Extended Euclidean Algorithm}\label{alg:xgcd} 1968\index{extended Euclidean algorithm} 1969Suppose$a$and$b$are integers and let$g=\gcd(a,b)$. 1970This algorithm finds~$d$,$x$and$y$such that$ax+by = g$. 1971We describe only the steps when$a>b\geq 0$, since one 1972can easily reduce to this case. 1973\begin{steps} 1974\item{} [Initialize] Set$x\assign 1$,$y\assign 0$,$r \assign 0$,$s \assign 1$. 1975\item{} [Finished?] \label{alg:xgcd_2} If$b=0$, set$g\assign a$and terminate. 1976\item{} [Quotient and Remainder] 1977Use Algorithm~\ref{alg:division} to write$a = qb + c$with$0\leq c<b$. 1978\item{} [Shift] 1979Set$(a, b, r, s, x, y) \assign (b, c, x-qr, y-qs, r, s)$1980and go to step~\ref{alg:xgcd_2}. 1981\end{steps} 1982\end{algorithm} 1983\begin{proof} 1984This algorithm is the same as Algorithm~\ref{alg:gcd}, except that we 1985keep track of extra variables$x,y,r,s$, so it terminates and when 1986it terminates$d=\gcd(a,b)$. 1987We omit the rest of the inductive proof that the algorithm 1988is correct, and instead refer the reader to 1989\cite[\S1.2.1]{knuth1} which contains a detailed proof 1990in the context of a discussion of how one 1991writes mathematical proofs. 1992\end{proof} 1993 1994\begin{algorithm}{Inverse Modulo$n$}\label{alg:inversemod} 1995Suppose$a$and$n$are integers and$\gcd(a,n)=1$. 1996This algorithm finds an~$x$such that$ax\con 1\pmod{n}$. 1997\begin{steps} 1998\item{} [Compute Extended GCD] Use Algorithm~\ref{alg:xgcd} to compute 1999integers$x,y$such that$ax+ny=\gcd(a,n)=1$. 2000\item{} [Finished] Output$x$. 2001\end{steps} 2002\end{algorithm} 2003\begin{proof} 2004Reduce$ax+ny=1$modulo~$n$to see that$x$2005satisfies$ax\con 1\pmod{n}$. 2006\end{proof} 2007See Section~\ref{sec:comp_lin_eq} for implementations 2008of Algorithms~\ref{alg:xgcd} and \ref{alg:inversemod}. 2009 2010\begin{example} 2011Solve$17x \con 1\pmod{61}$. 2012First, we use Algorithm~\ref{alg:xgcd} to find$x, y$such that 2013$17x+61y=1: 2014\begin{align*} 2015\ul{61}&=3\cdot\ul{17}+\ul{10} & \ul{10} &=\ul{61} - 3\cdot\ul{17}\\ 2016\ul{17}&=1\cdot\ul{10}+\ul{7} & \ul{7} &=-\ul{61} + 4\cdot\ul{17}\\ 2017\ul{10}&=1\cdot \ul{7}+\ul{3} & \ul{3} &=2\cdot\ul{61} - 7\cdot\ul{17}\\ 2018\ul{3} &=2\cdot\ul{3} +\ul{1} & \ul{1} &=-5\cdot\ul{61}+18\cdot\ul{17} 2019\end{align*} 2020Thus17\cdot 18 + 61\cdot (-5) = 1$so$x=18$2021is a solution to$17x \con 1\pmod{61}$. 2022\end{example} 2023 2024 2025 2026\subsection{How to Compute$a^m\pmod{n}$}\index{compute!powers modulo$n$|nn} 2027\label{sec:compute_powers}\index{powering algorithm|nn} 2028Let~$a$and~$n$be integers, and~$m$a nonnegative integer. 2029In this section we describe an efficient algorithm to compute 2030$a^m\pmod{n}$. For the cryptography 2031applications in Chapter~\ref{ch:crypto},~$m$will have 2032hundreds of digits. 2033 2034The naive approach to computing$a^m\pmod{n}$is to simply compute 2035$a^m = a\cdot a \cdots a\pmod{n}$by repeatedly multiplying by~$a$and 2036reducing modulo~$m$. Note that after each arithmetic operation is 2037completed, we reduce the result modulo~$n$so that the sizes of the 2038numbers involved do not get too large. Nonetheless, this algorithm is 2039horribly inefficient because it takes$m-1$multiplications, which 2040is huge if~$m$has hundreds of digits. 2041 2042A much more efficient algorithm for computing$a^m\pmod{n}$involves 2043writing~$m$in binary, then expressing$a^m$as a product of 2044expressions$a^{2^i}$, for various~$i$. These latter expressions can 2045be computed by repeatedly squaring$a^{2^i}$. This more clever algorithm 2046is not simpler'', but it is vastly more efficient since the number 2047of operations needed grows with the number of binary digits of~$m$, whereas 2048with the naive algorithm above the number of operations is$m-1$. 2049 2050\begin{algorithm}{Write a number in binary}\label{alg:binary}% 2051\index{binary, writing number in} 2052Let$m$be a nonnegative integer. This algorithm writes~$m$in 2053binary, so it finds$\eps_i\in\{0,1\}$such that 2054$m=\sum_{i=0}^r \eps_i 2^i$with each$\eps_i\in\{0,1\}$. 2055\begin{steps} 2056\item{}[Initialize] Set$i\assign 0$. 2057\item{}[Finished?]\label{alg:binary_2} If$m=0$, terminate. 2058\item{}[Digit] 2059If~$m$is odd, set$\eps_i\assign 1$, otherwise$\eps_i\assign 0$. 2060Increment~$i$. 2061\item{}[Divide by$2$] 2062Set~$m \assign \left\lfloor\frac{m}{2}\right\rfloor$, the 2063greatest integer$\leq m/2$. Goto step \ref{alg:binary_2}. 2064\end{steps} 2065\end{algorithm} 2066 2067\begin{algorithm}{Compute Power}\label{alg:power} 2068Let~$a$and~$n$be integers and~$m$a nonnegative integer. 2069This algorithm computes$a^m$modulo~$n$. 2070\begin{steps} 2071\item{}[Write in Binary] Write~$m$in binary using Algorithm~\ref{alg:binary}, so 2072$
2073   a^m  = \prod_{\eps_i = 1} a^{2^i}\pmod{n}.
2074$2075\item{}[Compute Powers] Compute~$a$,$a^2$,$a^{2^2} = (a^2)^2$, 2076$a^{2^3} = (a^{2^2})^2$, etc., up 2077to$a^{2^r}$, where$r+1$is the number of binary 2078digits of~$m$. 2079\item{}[Multiply Powers] Multiply together the 2080$a^{2^i}$such that$\eps_i=1$, 2081always working modulo~$n$. 2082\end{steps} 2083\end{algorithm} 2084See Section~\ref{sec:comp_powermod} for 2085an implementation of Algorithms~\ref{alg:binary} and \ref{alg:power}. 2086 2087 2088 2089We can compute the last~$2$digits of$6^{91}$, by 2090finding$6^{91}\pmod{100}$. Make a table whose first column, labeled~$i$, 2091contains~$0$,~$1$,~$2$, etc. The second column, labeled~$m$, is got 2092by dividing the entry above it by~$2$and taking the integer part of 2093the result. The third column, labeled$\eps_i$, records whether or 2094not the second column is odd. The fourth column is computed by 2095squaring, modulo$n=100$, the entry above it. 2096 2097\begin{center} 2098\begin{tabular}{|c|c|c|c|}\hline 2099\quad$i$\quad\quad & \quad$m$\quad\quad 2100 & \quad$\eps_i$\quad \quad & \quad$6^{2^i}$\text{mod} 100\\\hline\hline 21010 & 91 & 1 & 6 \\\hline 21021 & 45 & 1 & 36\\\hline 21032 & 22 & 0 & 96\\\hline 21043 & 11 & 1 & 16\\\hline 21054 & 5 & 1 & 56\\\hline 21065 & 2 & 0 & 36\\\hline 21076 & 1 & 1 & 96\\\hline 2108\end{tabular} 2109\end{center} 2110We have 2111$$2112 6^{91} \con 6^{2^6}\cdot 6^{2^4} \cdot 6^{2^3}\cdot 6^2 \cdot 6 2113 \con 96 \cdot 56 \cdot 16 \cdot 36 \cdot 6 2114 \con 56\pmod{100}. 2115$$ 2116That is easier than multiplying~$6$by itself$91$times. 2117 2118\begin{remark} 2119Alternatively, we could simplify the computation using 2120Theorem~\ref{thm:fermatlittle}. By that theorem, 2121$6^{\vphi(100)} \con 1\pmod{100}$, so since 2122$\vphi(100) = \vphi(2^2\cdot 5^2) = (2^2-2)\cdot(5^2-5)=40$, 2123we have$6^{91} \con 6^{11} \pmod{100}$. 2124\end{remark} 2125 2126\section{Finding Primes} 2127\label{sec:prob_prime_test}\index{primes!testing for} 2128 2129\begin{theorem}[Pseudoprimality]\index{primality test!pseudoprime} 2130\ithm{Pseudoprimality} 2131An integer~$p>1$is prime if and only if 2132for {\em every}$a\not\con 0\pmod{p}$, 2133$$2134 a^{p-1}\con 1\pmod{p}. 2135$$ 2136\end{theorem} 2137\begin{proof} 2138If~$p$is prime, then the statement follows from 2139Proposition~\ref{prop:wilson}. If~$p$is composite, 2140then there is a divisor~$a$of~$p$with$a\neq 1,p$. 2141If$a^{p-1}\con 1\pmod{p}$, then$p\mid a^{p-1} -1$. 2142Since$a\mid p$, we have$a \mid a^{p-1} -1$hence 2143$a\mid 1$, a contradiction. 2144\end{proof} 2145Suppose$n\in\N$. Using this theorem and Algorithm~\ref{alg:power}, we 2146can either quickly prove that~$n$is not prime, or convince ourselves 2147that~$n$is likely prime (but not quickly prove that~$n$is prime). 2148For example, if$2^{n-1}\not\con 1\pmod{n}$, then we have proved 2149that~$n$is not prime. On the other hand, if$a^{n-1}\con 1\pmod{n}$2150for a few~$a$, it seems likely'' that~$n$is prime, and we loosely 2151refer to such a number that seems prime for several bases as a 2152\defn{pseudoprime}. 2153 2154There are composite numbers~$n$(called \defn{Carmichael numbers}) 2155with the amazing property that 2156$a^{n-1}\con 1\pmod{n}$for {\em all}$a$with$\gcd(a,n)=1$. The 2157first Carmichael number is$561$, and it is a theorem that there 2158are infinitely many such numbers (\cite{carmichael}). 2159 2160\begin{example} 2161Is~$p=323$prime? 2162We compute$2^{322}\pmod{323}$. 2163Making a table as above, we have 2164\begin{center} 2165\begin{tabular}{|cccc|}\hline 2166\quad$i$\quad\quad & \quad$m$\quad\quad 2167 & \quad$\eps_i$\quad \quad & \quad$2^{2^i}$\text{mod} 323\\\hline 21680 & 322 & 0 & 2 \\\hline 21691 & 161 & 1 & 4 \\\hline 21702 & 80 & 0 & 16 \\\hline 21713 & 40 & 0 & 256 \\\hline 21724 & 20 & 0 & 290 \\\hline 21735 & 10 & 0 & 120 \\\hline 21746 & 5 & 1 & 188 \\\hline 21757 & 2 & 0 & 137 \\\hline 21768 & 1 & 1 & 35 \\\hline 2177\end{tabular} 2178\end{center} 2179Thus 2180 $$2^{322} \con 4\cdot 188\cdot 35 \con 157\pmod{323},$$ 2181so$323$is not prime, though this computation gives no information 2182about$323$factors as a product of primes. 2183In fact, one finds that$323 = 17\cdot 19$. 2184\end{example} 2185 2186It's possible to easily prove that a large number is composite, but the 2187proof does not easily yield a factorization. For example if 2188$$2189 n = 95468093486093450983409583409850934850938459083, 2190$$ 2191then$2^{n-1}\not\con 1\pmod{n}$, so~$n$is composite. 2192 2193Another practical primality test is the Miller-Rabin test,\index{primality test!Miller-Rabin} which has 2194the property that each time it is run on a number~$n$it either 2195correctly asserts that the number is definitely not prime, or that it is 2196probably prime, and the probability of correctness goes up with each 2197successive call. For a precise statement and implementation 2198of Miller-Rabin, along with proof of correctness, see 2199Section~\ref{sec:comp_primality}. 2200If Miller-Rabin is called~$m$times on~$n$and in 2201each case claims that~$n$is probably prime, then 2202one can in a precise sense bound the probability 2203that~$n$is composite in terms of~$m$. 2204For an implementation of Miller-Rabin, see Listing~\ref{listing:Miller-Rabin 2205 Primality Test} in Chapter~\ref{ch:computing}. 2206 2207%\subsection{A Polynomial Time Deterministic Primality Test} 2208\index{primality test!deterministic} \index{deterministic primality 2209 test} 2210%Though the practical methods for deciding primality with high 2211%probability discussed above is efficient in practice, 2212Until recently it was an open problem to give an algorithm (with proof) 2213that decides whether or not any integer is prime in time bounded by a 2214polynomial in the number of digits of the integer. Agrawal, Kayal, 2215and Saxena recently found the first polynomial-time primality test 2216(see \cite{agrawal:primes}). We will not discuss their algorithm 2217further, because for our applications to cryptography Miller-Rabin 2218or pseudoprimality tests will be sufficient. 2219 2220 2221\section{The Structure of$(\zmod{p})^*$} 2222\label{sec:primitive} 2223This section is about the structure of the group$(\zmod{p})^*$of 2224units modulo a prime number~$p$.\index{units!of$\zmod{p}$are cyclic|nn} 2225The main result is that this group is always cyclic. 2226We will use this result later in Chapter~\ref{ch:reciprocity} 2227in our proof of quadratic reciprocity. 2228 2229\begin{definition}[Primitive root]\label{defn:primroot} 2230A \defn{primitive root} modulo an integer~$n$is an element of 2231$(\zmod{n})^*$of order$\vphi(n)$. 2232\end{definition} 2233We will prove that there is a primitive root modulo every 2234prime~$p$. Since the unit group 2235$(\zmod{p})^*$has order$p-1$, this implies that 2236$(\zmod{p})^*$is a cyclic group, a fact this will be extremely useful, 2237since it completely determines the structure of$(\zmod{p})^*$as an 2238abelian group. 2239 2240If~$n$is an odd prime power, then there is a primitive root 2241modulo~$n$(see \exref{ch:cong}{ex:prim2}), but there is no primitive root 2242modulo the prime power~$2^3$, and hence none mod$2^n$for 2243$n\geq 3$(see \exref{ch:cong}{ex:prim1}). 2244\index{primitive root!mod power of two} 2245 2246Section~\ref{sec:polys_zp} is the key input to our proof that 2247$(\zmod{p})^*$is cyclic; here we show that for every divisor~$d$of$p-1$2248there are exactly~$d$elements of$(\zmod{p})^*$whose order divides~$d$. 2249We then use this result in Section~\ref{sec:struc_zp} to produce an 2250element of$(\zmod{p})^*$of order~$q^r$when~$q^r$is a prime power that 2251exactly divides$p-1$(i.e.,$q^r$divides$p-1$, but$q^{r+1}$does not 2252divide$p-1$), and multiply together these elements to obtain an element 2253of$(\zmod{p})^*$of order$p-1$. 2254 2255\subsection{Polynomials over$\zmod{p}$}\label{sec:polys_zp} 2256\index{polynomials!over$\zmod{p}$} 2257 2258The polynomials$x^2-1$has four roots in$\zmod{8}$, namely 2259$1$,$3$,$5$, and$7$. In contrast, the following proposition 2260shows that a polynomial of degree~$d$over a field, 2261such as$\zmod{p}$, can have at most$d$roots. 2262\begin{proposition}[Root Bound]\label{prop:atmost} 2263\iprop{root bound} 2264Let$f\in k[x]$be a nonzero polynomial 2265over a field$k$. Then there are at most 2266$\deg(f)$elements$\alpha\in k$such that$f(\alpha)=0$. 2267\end{proposition} 2268\begin{proof} 2269We prove the proposition by induction on$\deg(f)$. The cases in 2270which 2271$\deg(f)\leq 1$are clear. Write 2272$f = a_n x^n + \cdots a_1 x + a_0$. If 2273$f(\alpha)=0then 2274\begin{align*} 2275 f(x) &= f(x) - f(\alpha)\\ 2276 &= a_n(x^n-\alpha^n) + \cdots a_1(x-\alpha) + a_0(1-1)\\ 2277 &= (x-\alpha)(a_n(x^{n-1}+\cdots + \alpha^{n-1}) + \cdots + a_2(x+\alpha) + a_1)\\ 2278 &= (x-\alpha)g(x), 2279\end{align*} 2280for some polynomialg(x)\in k[x]$. 2281Next suppose that$f(\beta)=0$with$\beta\neq \alpha$. Then 2282$(\beta-\alpha) g(\beta) = 0$, so, since$\beta-\alpha\neq 0$, 2283we have$g(\beta)=0$. 2284By our inductive hypothesis,~$g$has at most$n-1$roots, so 2285there are at most$n-1$possibilities for~$\beta$. 2286It follows that~$f$has at most~$n$roots. 2287\end{proof} 2288 2289\begin{proposition}\label{prop:dsols} 2290Let~$p$be a prime number and let~$d$be a divisor 2291of$p-1$. Then$f = x^d-1\in(\zmod{p})[x]$has 2292exactly~$d$roots in$\zmod{p}$. 2293\end{proposition} 2294\begin{proof} 2295Let$e=(p-1)/d. We have 2296\begin{align*} 2297x^{p-1} - 1 &= (x^d)^e - 1\\ 2298 &= (x^d - 1)((x^d)^{e-1} + (x^d)^{e-2} + \cdots + 1)\\ 2299 &= (x^d - 1)g(x), 2300\end{align*} 2301whereg\in (\zmod{p})[x]$and 2302$\deg(g) = de-d = p-1-d$. 2303Theorem~\ref{thm:fermatlittle} 2304implies that$x^{p-1}-1$has 2305exactly$p-1$roots in$\zmod{p}$, since every nonzero element of 2306$\zmod{p}$is a root! By Proposition~\ref{prop:atmost},~$g$2307has {\em at most}$p-1-d$roots and$x^d-1$has at most~$d$roots. 2308Since a root of$(x^d-1)g(x)$is a root of either$x^d-1$or$g(x)$2309and$x^{p-1}-1$has$p-1$roots,~$g$must have exactly$p-1-d$roots 2310and$x^d-1$must have exactly~$d$roots, as claimed. 2311\end{proof} 2312 2313We pause to reemphasize that the analogue of 2314Proposition~\ref{prop:dsols} is false when~$p$is replaced by a 2315composite integer~$n$, since a root mod~$n$of a product of two 2316polynomials need not be a root of either factor. 2317For example,$f = x^2-1\in \zmod{15}[x]$has 2318the four roots$1$,$4$,$11$, and$14$. 2319 2320 2321\subsection{Existence of Primitive Roots}\label{sec:struc_zp}% 2322\index{primitive root!existence} 2323Recall from Section~\ref{sec:flittle} that the \defn{order} of an 2324element$x$in a finite group is the smallest~$m\geq 1$such that 2325$x^m=1$. In this section, we prove that$(\zmod{p})^*$is cyclic by 2326using the results of Section~\ref{sec:polys_zp} to produce an element 2327of$(\zmod{p})^*$of order~$d$for each prime power divisor~$d$of 2328$p-1$, and then we multiply these together to obtain an element of 2329order$p-1$. 2330 2331We will use the following lemma to assemble elements of 2332each order dividing$p-1$to produce an 2333element of order$p-1$. 2334\begin{lemma}\label{lem:ordmult} 2335 Suppose$a,b\in(\zmod{n})^*$have orders~$r$and~$s$, respectively, 2336 and that$\gcd(r,s)=1$. Then$ab$has order$rs$. 2337\end{lemma} 2338\begin{proof} 2339This is a general fact about commuting elements of any group; our proof 2340only uses that$ab=ba$and nothing special about$(\zmod{n})^*$. Since 2341$$2342 (ab)^{rs} = a^{rs}b^{rs}=1, 2343$$ 2344the order of$ab$is a divisor of$rs$. 2345Write this divisor as$r_1 s_1$where$r_1\mid r$2346and$s_1\mid s$. 2347Raise both sides of the equation 2348$$2349 a^{r_1 s_1}b^{r_1 s_1} = (ab)^{r_1 s_1} = 1. 2350$$ 2351to the power$r_2 = r/r_1\$ to obtain<