CoCalc Public Fileswww / 168 / refs / stein-numthry.texOpen with one click!
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}
170
To 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}
183
\addcontentsline{toc}{chapter}{\numberline{}Preface}
184
185
This is a textbook about prime
186
numbers, congruences, basic public-key cryptography, quadratic
187
reciprocity, continued fractions, elliptic curves, and number
188
theory algorithms. We assume the
189
reader has some familiarity with groups, rings, and fields, and
190
for Chapter~\ref{ch:computing} some programming experience.
191
This book grew out of an undergraduate course that the
192
author taught at Harvard University in 2001 and 2002.
193
194
195
196
\vspace{1.5ex}\noindent{}{\bf Notation and Conventions.}
197
We let $\N=\{1,2,3,\ldots\}$ denote the natural numbers, and use the
198
standard notation $\Z$, $\Q$, $\R$, and $\C$ for the rings of integer,
199
rational, real, and complex numbers, respectively.\index{notation} In
200
this book we will use the words proposition, theorem, lemma, and
201
corollary as follows. Usually a proposition is a less important or
202
less fundamental assertion, a theorem a deeper culmination of ideas, a
203
lemma something that we will use later in this book to prove a
204
proposition or theorem, and a corollary an easy consequence of a
205
proposition, theorem, or lemma.
206
207
\vspace{1.5ex}\noindent{}{\bf Acknowledgements.} Brian Conrad and Ken
208
Ribet made a large number of clarifying comments and suggestions
209
throughout the book. Baurzhan Bektemirov, Lawrence Cabusora, and
210
Keith Conrad read drafts of this book and made many comments.
211
Frank Calegari used the course when teaching Math 124 at Harvard,
212
and he and his students provided much feedback.
213
Noam Elkies made comments and suggested
214
\exref{ch:reciprocity}{ex:rec8}. Seth Kleinerman wrote a version of
215
Section~\ref{sec:contfrac_e} as a class project.
216
%Hendrik Lenstra made
217
%helpful remarks about how to present his factorization algorithm.
218
Samit Dasgupta, George Stephanides,
219
Kevin Stern, and Heidi
220
Williams all suggested corrections. I also benefited from
221
conversations with Henry Cohn and David Savitt.
222
I 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
237
In Section~\ref{sec:fundamental_thm} we describe how the integers are
238
built out of the prime numbers $2, 3, 5, 7, 11,\ldots$. In
239
Section~\ref{sec:primeseq} we discuss theorems about the set of primes
240
numbers\index{primes}, starting with Euclid's\index{Euclid} proof that
241
this set is infinite, then explore the distribution of primes via the
242
prime number theorem and the Riemann Hypothesis (without proofs).
243
244
\section{Prime Factorization}
245
\label{sec:fundamental_thm}
246
\subsection{Primes}\label{sec:primes}
247
The set of {\em natural numbers}\index{natural numbers} is
248
$$
249
\N = \{1,2,3,4,\ldots\},
250
$$
251
and 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]
280
If $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
283
that~$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}
286
For example, we have $2 \mid 6$ and $-3\mid 15$.
287
Also, all integers divide\index{divides}~$0$, and~$0$ divides
288
only~$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}
346
An integer $n>1$ is \defn{prime} if it the only positive
347
divisors of $n$ are $1$ and~$n$.
348
We 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
356
The number~$1$ is neither prime nor composite. The first few
357
primes of~$\N$ are $$
358
2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
359
47, 53, 59, 61, 67, 71, 73, 79, \ldots, $$
360
and the first few
361
composites are $$
362
4,6,8,9,10,12, 14, 15, 16, 18, 20, 21, 22, 24, 25,
363
26, 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.
369
In this book we consider neither $-1$ nor $1$ to be prime.
370
\end{remark}
371
372
Every 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}%
377
Every natural number can be written as a product of primes
378
uniquely up to order.
379
\end{theorem}
380
Note that primes are the products with only one factor and~$1$ is the
381
empty product.
382
383
\begin{remark}
384
Theorem~\ref{thm:fundamental}, which we will prove in
385
Section~\ref{sec:proof_fundamental}, is trickier to prove than you
386
might first think. For example, unique factorization\index{unique
387
factorization} fails in the ring
388
$$
389
\Z[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b\in\Z\} \subset \C,
390
$$
391
where~$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}
399
We will use the notion of greatest common divisor of two integers to
400
prove that if~$p$ is a prime and $p\mid ab$, then $p\mid a$ or $p\mid
401
b$. Proving this is the key step in our proof of
402
Theorem~\ref{thm:fundamental}.
403
404
\begin{definition}[Greatest Common Divisor]
405
Let
406
$$
407
\gcd(a,b)=\max\left\{d\in \Z : d \mid a\text{ and } d\mid b\right\},
408
$$
409
unless both~$a$ and~$b$ are~$0$ in which case
410
$\gcd(0,0)=0$.
411
\end{definition}
412
For example,
413
$\gcd(1,2)=1$,
414
$\gcd(6,27)=3$, and
415
for any~$a$,
416
$\gcd(0,a)=\gcd(a,0)=a$.
417
418
If $a\neq 0$, the greatest common divisor exists because if $d\mid a$
419
then $d\leq a$, and there are only $a$ positive integers $\leq a$.
420
Similarly, the $\gcd$ exists when $b\neq 0$.
421
422
\begin{lemma}\label{lem:gcdprops}
423
For 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
430
are 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}
441
Suppose $a,b,n\in\Z$. Then
442
$\gcd(a,b) = \gcd(a,b-an)$.
443
\end{lemma}
444
\begin{proof}
445
By 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
451
Assume for the moment that we have already proved
452
Theorem~\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
454
Theorem~\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
457
5^2\cdot {\bf 17}$, so $\gcd(a,b) = 17$. It turns out that the
458
greatest common divisor of two integers, even huge numbers (millions
459
of digits), is surprisingly easy to compute using
460
Algorithm~\ref{alg:gcd} below, which computes $\gcd(a,b)$ without
461
factoring~$a$ or~$b$. \index{compute!greatest common divisor}
462
463
To motivate Algorithm~\ref{alg:gcd}, we compute $\gcd(2261,1275)$ in
464
a 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
486
For us an \defn{algorithm} is a finite sequence of instructions that
487
can be followed to perform a specific task, such as a sequence of
488
instructions in a computer program, which must terminate on
489
any valid input. The word ``algorithm'' is sometimes used more
490
loosely (and sometimes more precisely) than defined here, but this
491
definition 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
496
computes 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,
498
since it is just the familiar long division algorithm.
499
\end{algorithm}
500
501
We 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
$$
506
so $q=1$ and $r=986$.
507
Notice that if a natural number~$d$ divides both $2261$ and $1275$,
508
then~$d$ divides their difference $986$ and~$d$ still divides $1275$.
509
On the other hand, if~$d$ divides both $1275$ and $986$, then it has
510
to divide their sum $2261$ as well! We have made progress:
511
$$\gcd(2261,1275) = \gcd(1275,986).$$
512
This equality also follows by repeated application of
513
Lemma~\ref{lem:gcdprops}.
514
Repeating, we have
515
$$1275 = 1\cdot 986 + 289,$$
516
so $\gcd(1275,986)=\gcd(986,289)$.
517
Keep going:
518
\begin{align*}
519
986&=3\cdot 289 + 119\\
520
289&=2\cdot 119 + 51\\
521
119&=2\cdot 51 + 17.
522
\end{align*}
523
Thus $\gcd(2261,1275)=\cdots=\gcd(51,17)$, which is $17$
524
because $17\mid 51$. Thus
525
$$\gcd(2261,1275)=17.$$
526
Aside from some tedious arithmetic, that computation was systematic,
527
and it was not necessary to factor any integers (which
528
is something we do not know how to do quickly if the numbers
529
involved have hundreds of digits).
530
\begin{algorithm}{Greatest Common Division}
531
\label{alg:gcd}\index{gcd algorithm}
532
\index{compute!gcd}
533
Given 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|)$,
537
so we may replace $a$ and $b$ by their absolute value and hence
538
assume $a, b \geq 0$. If $a=b$ output $a$ and
539
terminate. 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
544
step \ref{alg:gcd_usediv}.
545
\end{steps}
546
\end{algorithm}
547
\begin{proof}
548
Lemmas~\ref{lem:gcdprops}--\ref{lem:gcdprops2}
549
imply that $\gcd(a,b) = \gcd(b,r)$ so the gcd does not
550
change in step \ref{alg:gcd_shift}.
551
Since the remainders form a decreasing sequence of nonnegative
552
integers, the algorithm terminates.
553
\end{proof}
554
See Section~\ref{sec:comp_gcd} for an implementation of
555
Algorithm~\ref{alg:gcd}.
556
557
\begin{example}
558
Set $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
565
we can just as easily do an example that is ten times
566
as big, an observation that will be important in the
567
proof of Theorem~\ref{thm:euclid} below.
568
\begin{example}\label{ex:gcd10}
569
Set $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}
576
For 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}
604
Since $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$.
606
By Lemma~\ref{lem:gcdmul},
607
$\gcd(a,b) = \gcd(n c_1, nc_2) = n\gcd(c_1, c_2)$,
608
so $n$ divides $\gcd(a,b)$.
609
\end{proof}
610
611
At this point it would be natural to formally analyze the complexity
612
of Algorithm~\ref{alg:gcd}. We will not do this, because the main
613
reason we introduced Algorithm~\ref{alg:gcd} is that it will allow us
614
to prove Theorem~\ref{thm:fundamental}, and we have not chosen to
615
formally analyze the complexity of the other algorithms in this book.
616
For an extensive analysis of the complexity of
617
Algorithm~\ref{alg:gcd}, see \cite[\S4.5.3]{knuth2}.
618
619
With Algorithm~\ref{alg:gcd}, we can prove that if a prime divides the
620
product of two numbers, then it has got to divide one of them. This
621
result is the key to proving that prime factorization
622
is unique.
623
\begin{theorem}[Euclid]\label{thm:euclid}%
624
\index{Euclid's theorem!on divisibility}%
625
\ithm{Euclid}
626
Let~$p$ be a prime and $a, b\in \N$.
627
If $p\mid ab$ then $p\mid a$ or $p\mid b$.
628
\end{theorem}
629
You might think this theorem is ``intuitively obvious'', but
630
that might be
631
because the fundamental theorem of arithmetic\index{fundamental
632
theorem of arithmetic} (Theorem~\ref{thm:fundamental}) is deeply
633
ingrained in your intuition. Yet Theorem~\ref{thm:euclid} will be
634
needed 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}
646
In this section, we prove that every natural number factors as a
647
product of primes.
648
Then we discuss the difficulty of finding such a decomposition
649
in practice. We will wait until Section~\ref{sec:proof_fundamental}
650
to prove that factorization is unique.
651
652
As a first example, let $n=1275$. The sum of the digits
653
of $n$ is divisible by $3$, so $n$ is divisible by $3$ (see
654
Proposition~\ref{prop:div3}), and we have $n=3\cdot 425$.
655
The number $425$ is divisible by $5$, since its last digit
656
is $5$, and we have $1275 = 3\cdot 5 \cdot 85$. Again,
657
dividing $85$ by $5$, we have $1275 = 3\cdot 5^2 \cdot 17$,
658
which 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$.
663
Generalizing this process proves the following proposition:
664
\begin{proposition}\label{prop:numbers_factor}\iprop{prime factorization}
665
Every natural number is a product of primes.
666
\end{proposition}
667
\begin{proof}
668
Let~$n$ be a natural number. If $n=1$, then~$n$ is the empty
669
product of primes.
670
If $n$ is prime, we are done.
671
If $n$ is composite, then $n=ab$ with $a,b<n$. By induction,~$a$
672
and~$b$ are products of primes, so~$n$ is also a product of primes.
673
\end{proof}
674
675
Two questions immediately arise: (1) is this factorization unique, and
676
(2) how quickly can we find such a factorization? Addressing (1),
677
what if we had done something differently when breaking apart $1275$
678
as a product of primes? Could the primes that show up be different?
679
Let'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
681
by Theorem~\ref{thm:fundamental} above. We will prove uniqueness
682
of the prime factorization of
683
any integer in Section~\ref{sec:proof_fundamental}.
684
685
Regarding (2), there are algorithms for integer factorization; e.g., in
686
Sections~\ref{sec:ecm} and \ref{sec:alg_intfac} we will study and
687
implement some of them. It is a major open problem to decide
688
how fast integer factorization algorithms can be.
689
\begin{openproblem}\index{open problem!fast integer factorization}
690
\index{factorization!difficulty of}
691
Is there an algorithm which can factor any
692
integer~$n$ in polynomial time? (See below
693
for the meaning of polynomial time.)
694
\end{openproblem}
695
By \defn{polynomial time} we mean that there is a
696
polynomial $f(x)$ such that for any~$n$ the number of steps needed by
697
the algorithm to factor~$n$ is less than $f(\log_{10}(n))$. Note
698
that $\log_{10}(n)$ is an approximation for the number of digits
699
of the input~$n$ to the algorithm.
700
701
Peter Shor \cite{shor}\index{Shor} devised a polynomial time algorithm
702
for factoring integers on quantum computers\index{quantum
703
computer}\index{factorization!quantum}. We will not discuss his
704
algorithm further, except to note that in 2001 IBM researchers
705
built a quantum computer that used Shor's algorithm to factor $15$ (see
706
\cite{quantum15, ibm:shor15}).
707
708
You can earn money by factoring certain large integers. Many
709
cryptosystems would be easily broken if factoring certain large
710
integers were easy. Since nobody has proven that factoring integers
711
is difficult, one way to increase confidence that factoring is
712
difficult is to offer cash prizes for factoring certain integers. For
713
example, until recently there was a \$10000 bounty on factoring the
714
following $174$-digit integer (see \cite{rsa:challenge}):
715
$$
716
\begin{array}{l}
717
1881988129206079638386972394616504398071635633794173827007\\
718
6335642298885971523466548531906060650474304531738801130339\\
719
6716199692321205734031879550656996221305168759307650257059
720
\end{array}
721
$$
722
This number is known as RSA-576\index{RSA-576} since it has 576
723
digits when written in binary (see Section~\ref{sec:compute_powers}
724
for more on binary numbers). It was factored at the German
725
Federal Agency for Information Technology Security in December
726
2003 (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
$$
736
The previous RSA challenge was the $155$-digit number
737
$$
738
\begin{array}{l}
739
1094173864157052742180970732204035761200373294544920599091\\
740
3842131476349984288934784717997257891267332497625752899781\\
741
833797076537244027146743531593354333897.
742
\end{array}$$
743
It was factored on 22 August 1999 by a group of sixteen researchers
744
in four months on a cluster of 292 computers (see \cite{rsa155}).
745
They found that RSA-155\index{RSA-155} is the product of the following two
746
$78$-digit primes:
747
\begin{align*}
748
p &= 10263959282974110577205419657399167590071656780803806\\
749
&\hspace{4ex} 6803341933521790711307779\\
750
q &= 10660348838016845482092722036001287867920795857598929\\
751
&\hspace{4ex} 1522270608237193062808643.
752
\end{align*}
753
The next RSA challenge is RSA-640:
754
$$
755
\begin{array}{l}
756
31074182404900437213507500358885679300373460228427275457201619\\
757
48823206440518081504556346829671723286782437916272838033415471\\
758
07310850191954852900733772482278352574238645401469173660247765\\
759
2346609,
760
\end{array}
761
$$
762
and its factorization is worth \$20000.
763
764
These RSA numbers were factored using an algorithm called the number
765
field sieve (see \cite{lenstras:nfs}), which is the best-known general
766
purpose factorization algorithm. A description of how the number
767
field sieve works is beyond the scope of this book. However, the
768
number field sieve makes extensive use of the elliptic curve
769
factorization 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}
774
We are ready to prove Theorem~\ref{thm:fundamental}
775
using the following idea.
776
Suppose we have two factorizations of~$n$. Using
777
Theorem~\ref{thm:euclid} we cancel common primes from each factorization,
778
one prime at a time. At the end,
779
we discover that the factorizations must
780
consist of exactly the same primes. The
781
technical 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
$$
791
Suppose that
792
$$n = q_1 q_2 \cdots q_m$$
793
is another expression of~$n$ as a product of primes.
794
Since
795
$$p_1 \mid n = q_1 (q_2 \cdots q_m),$$
796
Euclid'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
799
Now cancel $p_1$ and $q_i$, and repeat the above argument. Eventually,
800
we 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}
807
This section is concerned with three questions:
808
\begin{enumerate}
809
\item Are there infinitely many primes?
810
\item Given $a,b\in\Z$,
811
are there infinitely many primes of the form $ax+b$?
812
\item How are the primes spaced along the number line?
813
\end{enumerate}
814
We first show that there are infinitely
815
many primes, then state Dirichlet's theorem
816
\index{theorem!of Dirichlet} that if $\gcd(a,b)=1$,
817
then $ax+b$ is a prime for infinitely many values of~$x$. Finally, we
818
discuss the Prime Number Theorem\index{prime number theorem}
819
which asserts that there are
820
asymptotically $x/\log(x)$ primes less than~$x$,
821
and we make a connection between this asymptotic formula
822
and 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}
828
Each number on the left in the following table is prime.
829
We will see soon that this pattern does not continue
830
indefinitely, but something similar works.
831
\begin{align*}
832
3 &= 2+1\\
833
7 &= 2\cdot 3 + 1\\
834
31 &= 2\cdot 3 \cdot 5 + 1\\
835
211 &= 2\cdot 3 \cdot 5 \cdot 7 + 1\\
836
2311 &= 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1
837
\end{align*}
838
839
\begin{theorem}[Euclid]\label{thm:euclid_primes}
840
There are infinitely many primes.\ithm{infinitely many primes}
841
\end{theorem}
842
\begin{proof}
843
Suppose that $p_1, p_2, \ldots, p_n$ are~$n$ distinct primes.
844
We construct a prime $p_{n+1}$ not equal to any of $p_1,\ldots, p_n$
845
as follows. If
846
\begin{equation}\label{eqn:infprime}
847
N=p_1 p_2 p_3 \cdots p_n + 1,
848
\end{equation}
849
then by Proposition~\ref{prop:numbers_factor} there is a factorization
850
$$
851
N = q_1 q_2 \cdots q_m
852
$$
853
with each~$q_i$ prime and $m\geq 1$.
854
If $q_1 = p_i$ for some~$i$, then $p_i\mid{}N$.
855
Because of (\ref{eqn:infprime}), we also have
856
$p_i\mid{}N-1$, so $p_i\mid{} 1=N-(N-1)$, which
857
is a contradiction.
858
Thus the prime $p_{n+1} = q_1$ is not in the list $p_1,\ldots, p_n$,
859
and we have constructed our new prime.
860
\end{proof}
861
862
For example,
863
$$
864
2\cdot 3 \cdot 5 \cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509.
865
$$
866
Multiplying together the first~$6$ primes and adding~$1$ doesn't
867
produce a prime, but it produces an integer that is merely
868
divisible 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}
879
The Sieve of Eratosthenes is an efficient way to enumerate all
880
primes up to~$n$. The sieve works by first writing down all
881
numbers up to $n$, noting that~$2$ is prime, and crossing off all
882
multiples of~$2$. Next, note that the first number not crossed off is~$3$,
883
which is prime, and cross off all multiples of~$3$, etc.
884
Repeating this process, we obtain a list of the primes up to~$n$.
885
Formally, the algorithm is as follows:
886
\begin{algorithm}{Sieve of Eratosthenes}\label{alg:sieve}
887
Given a positive integer $n$, this algorithm computes a list of the
888
primes up to $n$.
889
\begin{steps}
890
\item{}[Initialize] Let $X\assign [3,5,\ldots]$ be the list
891
of all odd integers between $3$ and $n$. Let $P\assign [2]$ be the list
892
of primes found so far.
893
\item{}[Finished?]\label{alg:sieve_2}
894
Let $p$ to be the first element of $X$.
895
If $p\geq \sqrt{n}$, append each element of~$X$
896
to~$P$ and terminate. Otherwise append $p$ to $P$.
897
\item{}[Cross Off]
898
Set~$X$ equal to the sublist of elements in~$X$ that
899
are not divisible by~$p$.
900
Go to step \ref{alg:sieve_2}.
901
\end{steps}
902
\end{algorithm}
903
For example, to list the primes $\leq 40$ using the sieve, we
904
proceed 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].$$
906
We append $3$ to $P$ and cross off all multiples of $3$ to obtain
907
the new list
908
$$X = [5,7,11,13,17,19,23,25,29,31,35,37].$$
909
Next we append $5$ to $P$, obtaining $P=[2,3,5]$, and cross off
910
the multiples of $5$, to obtain $X = [7,11,13,17,19,23,29,31,37].$
911
Because $7^2\geq 40$, we append $X$ to $P$ and find that the
912
primes 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}]
917
The part of the algorithm that is not clear is that
918
when the first element $a$ of $X$ satisfies $a\geq \sqrt{n}$,
919
then each element of $X$ is prime.
920
To see this, suppose $m$ is in $X$, so
921
$\sqrt{n} \leq m\leq n$ and that~$m$ is divisible by
922
no prime that is $\leq \sqrt{n}$. Write $m=\prod p_i^{e_i}$ with
923
the $p_i$ distinct primes and $p_1<p_2<\ldots$. If $p_i>\sqrt{n}$
924
for each~$i$ and there is more than one~$p_i$, then $m>n$,
925
a contradiction. Thus some~$p_i$ is less than $\sqrt{n}$,
926
which also contradicts out assumptions on~$m$.
927
\end{proof}
928
See Section~\ref{sec:comp_enum_primes} for an implementation of
929
Algorithm~\ref{alg:sieve}.
930
931
932
\subsection{The Largest Known Prime}\index{primes!largest known}
933
\index{largest known!prime}
934
Though Theorem~\ref{thm:euclid_primes} implies that there are infinitely
935
many primes, it still makes sense to ask the question
936
``What is the largest {\em known} prime?''
937
938
A \defn{Mersenne prime} is a prime of the form $2^q-1$.
939
According to \cite{caldwell:largestprime} the largest known prime
940
as of July 2004 is the Mersenne prime\index{primes!Mersenne}
941
$$
942
p = 2^{24036583}-1,
943
$$
944
which has $7235733$ decimal digits, so writing it out would fill
945
over $10$ books the size if this book.
946
Euclid's theorem implies that there definitely is a prime bigger than
947
this 7.2 million digit~$p$. Deciding whether or not a number
948
is prime is interesting, both as a motivating problem and
949
for applications to cryptography\index{cryptography}, as we will see in
950
Section~\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$}
954
Next we turn to primes of the form $ax+b$, where~$a$ and~$b$ are
955
fixed integers with $a>1$ and~$x$ varies over the natural numbers $\N$.
956
We assume that $\gcd(a,b)=1$, because otherwise there is no
957
hope that $ax+b$ is prime infinitely often.
958
For example, $2x+2=2(x+1)$ is only prime if $x=0$, and is
959
not 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}
963
There are infinitely many primes of the form $4x-1$.
964
\end{proposition}
965
Why might this be true? We list numbers of the form $4x-1$ and underline
966
those 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$$
969
It is plausible that underlined numbers would continue to appear
970
indefinitely.
971
972
\begin{proof}
973
Suppose $p_1, p_2,\ldots, p_n$ are distinct primes of the form $4x-1$. Consider
974
the number
975
$$
976
N = 4p_1 p_2 \cdots p_n - 1.
977
$$
978
Then $p_i \nmid N$ for any~$i$. Moreover, not every prime $p\mid N$
979
is 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
983
of the form $4x-1$ cannot be finite.
984
\end{proof}
985
Note that this proof does not work if $4x-1$ is replaced by $4x+1$,
986
since 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}
991
Set $p_1=3$, $p_2=7$. Then
992
$$
993
N = 4\cdot 3 \cdot 7 - 1 = \ul{83}
994
$$
995
is a prime of the form $4x-1$. Next
996
$$
997
N = 4\cdot 3 \cdot 7\cdot 83 - 1 = \ul{6971},
998
$$
999
which is again a prime of the form $4x-1$.
1000
Again:
1001
$$
1002
N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 - 1 = 48601811 = 61 \cdot \ul{796751}.
1003
$$
1004
This time $61$ is a prime, but it is of the form $4x+1 = 4\cdot 15+1$.
1005
However, $796751$ is prime and
1006
$796751 = 4\cdot 199188 - 1$.
1007
We are unstoppable:
1008
$$
1009
N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 \cdot 796751 - 1 = \ul{5591}\cdot 6926049421.
1010
$$
1011
This time the small prime, $5591$, is of the form $4x-1$ and the large
1012
one is of the form $4x+1$.
1013
\end{example}
1014
1015
\begin{theorem}[Dirichlet]\label{thm:dirichlet}
1016
\ithm{Dirichlet}
1017
Let~$a$ and~$b$ be integers with $\gcd(a,b)=1$.
1018
Then there are infinitely many primes of the form
1019
$ax+b$.
1020
\end{theorem}
1021
Proofs of this theorem typically use tools from advanced number
1022
theory, 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}
1028
We saw in Section~\ref{sec:inf_primes}
1029
that there are infinitely many primes.
1030
In order to get a sense for just how many primes there are,
1031
we consider a few warm-up questions.
1032
Then we consider some numerical evidence and state
1033
the prime number theorem, which gives an asymptotic answer
1034
to our question, and connect this theorem with a form
1035
of the Riemann Hypothesis.\index{Riemann Hypothesis}
1036
Our discussion of counting primes in this section is very cursory;
1037
for more details, read Crandall and Pomerance's excellent
1038
book \cite[\S1.1.5]{primenumbers}.
1039
1040
The following vague discussion is meant to motivate a precise way to
1041
measure the number of primes. How many natural numbers are even?
1042
Answer: Half of them. How many natural numbers are of the form
1043
$4x-1$? Answer: One fourth of them. How many natural numbers are
1044
perfect squares? Answer: Zero percent of all natural numbers, in the
1045
sense that the limit of the proportion of perfect squares to all
1046
natural 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
$$
1052
since the numerator is roughly $\sqrt{x}$ and
1053
$\lim_{x\ra\infty}\frac{\sqrt{x}}{x} = 0$.
1054
Likewise, it is an easy consequence of Theorem~\ref{thm:primenumber}
1055
below that zero percent of all natural numbers are prime
1056
(see \exref{ch:primes}{ex:fewprimes}).
1057
1058
We are thus led to ask another question: How many positive integers
1059
$\leq x$ are perfect squares? Answer: roughly $\sqrt{x}$. In the
1060
context of primes, we ask,
1061
\begin{question}
1062
How many natural numbers $\leq x$ are prime?
1063
\end{question}
1064
1065
Let
1066
$$
1067
\pi(x) = \#\{p\in \N : p \leq x \text{ is a prime}\}.
1068
$$
1069
For example,
1070
$$
1071
\pi(6) =\#\{2,3,5\} = 3.
1072
$$
1073
Some values of $\pi(x)$ are given in Table~\ref{tab:primes},
1074
and Figures~\ref{fig:pix} and \ref{fig:pix2} contain graphs of $\pi(x)$.
1075
These 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
1211
Gauss\index{Gauss} had a lifelong love of enumerating primes.
1212
Eventually he computed $\pi(3000000)$, though the author doesn't know
1213
whether or not Gauss got the right answer, which is $216816$. Gauss
1214
conjectured the following asymptotic formula for $\pi(x)$, which was
1215
later proved independently by Hadamard\index{Hadamard} and Vall\'ee
1216
Poussin\index{Vall\'ee Poussin} in 1896 (but will not be proved in
1217
this book):
1218
\begin{theorem}[Prime Number Theorem]\label{thm:primenumber}
1219
\ithm{prime number}
1220
The 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}
1223
We do nothing more here than motivate this deep theorem with
1224
a few further numerical observations.
1225
1226
The theorem implies that
1227
$$\lim_{x\ra \infty} \pi(x)/x = \lim_{x\ra \infty} 1/\log(x)=0,$$
1228
so 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.$$
1232
Thus $x/(\log(x)-a)$ is also asymptotic to $\pi(x)$ for
1233
any~$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
1245
1000& 168& 169.2690290604408165186256278\\
1246
2000& 303& 302.9888734545463878029800994\\
1247
3000& 430& 428.1819317975237043747385740\\
1248
4000& 550& 548.3922097278253264133400985\\
1249
5000& 669& 665.1418784486502172369455815\\
1250
6000& 783& 779.2698885854778626863677374\\
1251
7000& 900& 891.3035657223339974352567759\\
1252
8000& 1007& 1001.602962794770080754784281\\
1253
9000& 1117& 1110.428422963188172310675011\\
1254
10000& 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
1269
As 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
$$
1292
is a ``good'' approximation to $\pi(x)$, in the following
1293
precise 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}
1301
If $x=2$, then $\pi(2)=1$ and $\Li(2)=0$,
1302
but $\sqrt{2}\log(2) = 0.9802\ldots$, so the inequality
1303
is not true for $x\geq 2$, but $2.01$ is big enough.
1304
We will do nothing more to explain this conjecture,
1305
and settle for one numerical example.
1306
\begin{example}
1307
Let $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
1318
One of the best popular article on the prime number theorem and
1319
the 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
1326
to make a list of all primes up to $100$.
1327
1328
\item\label{ex:primesform} Prove that there are infinitely
1329
many primes of the form $6x-1$.\index{primes!of the form $6x-1$}
1330
1331
\item \label{ex:fewprimes}
1332
Use 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
1345
This chapter is about the ring $\zmod{n}$ of integers
1346
modulo~$n$.\index{$\zmod{n}$}
1347
First we discuss when linear equations modulo~$n$ have a solution,
1348
then introduce the Euler~$\vphi$ function and prove Fermat's Little
1349
Theorem and Wilson's theorem. Next we prove the Chinese Remainer
1350
Theorem, which addresses simultaneous solubility of several linear
1351
equations modulo coprime moduli. With these theoretical foundations
1352
in place, in Section~\ref{sec:arith_mod_n} we introduce algorithms for
1353
doing interesting computations modulo~$n$, including computing large
1354
powers quickly, and solving linear equations. We finish with a very
1355
brief 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}
1364
In this section we define the ring $\zmod{n}$ of integers modulo~$n$,
1365
introduce the Euler $\vphi$-function,\index{Euler!phi function}
1366
\index{phi@$\vphi$ function} and relate it to the
1367
multiplicative order\index{multiplicative!order}
1368
of certain elements of $\zmod{n}$.
1369
1370
If $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}$.
1372
Let $n\Z=(n)$ be the ideal of $\Z$ generated by~$n$.
1373
\begin{definition}[Integers Modulo $n$]
1374
The \defn{ring of integers modulo~$n$}
1375
is the quotient ring $\zmod{n}$ of equivalence classes of integers
1376
modulo~$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}
1387
For 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}
1396
We use the notation $\zmod{n}$ because $\zmod{n}$ is the quotient of
1397
the 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
1399
on~$\Z$ induces a ring structure on $\zmod{n}$. We often let~$a$
1400
or $a\pmod{n}$
1401
denote 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
1405
We 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$,
1408
since $7+3\Z = 1+3\Z$.
1409
1410
We can use that arithmetic in $\zmod{n}$ is well defined is to
1411
derive 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}
1414
A number $n\in\Z$ is divisible by~$3$ if and only if
1415
the sum of the digits of~$n$ is divisible by~$3$.
1416
\end{proposition}
1417
\begin{proof}
1418
Write
1419
$$n=a+10b+100c+\cdots,$$
1420
where the digits of~$n$ are $a$, $b$, $c$, etc.
1421
Since $10\con 1\pmod{3}$,
1422
$$
1423
n = a + 10b + 100c+\cdots \con a + b + c+\cdots \pmod{3},
1424
$$
1425
from 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
1431
are concerned with how to decide whether or not a linear equation of
1432
the form $ax\con b \pmod{n}$ has a solution modulo~$n$.
1433
Algorithms for {\em computing} solutions to $ax\con
1434
b\pmod{n}$ are the topic of Section~\ref{sec:arith_mod_n}.
1435
1436
First we prove a proposition that gives a criterion under
1437
which one can cancel a quantity from both sides of a congruence.
1438
\begin{proposition}[Cancellation]\label{prop:cancel}\iprop{cancellation}
1439
If $\gcd(c,n)=1$ and
1440
$$
1441
ac\con bc\pmod{n},
1442
$$
1443
then $a \con b\pmod{n}$.
1444
\end{proposition}
1445
\begin{proof}
1446
By definition
1447
$$
1448
n \mid ac - bc = (a-b)c.
1449
$$
1450
Since $\gcd(n,c)=1$, it follows
1451
from Theorem~\ref{thm:fundamental} that $n\mid a-b$, so
1452
$$
1453
a \con b\pmod{n},
1454
$$
1455
as claimed.
1456
\end{proof}
1457
1458
1459
1460
When~$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
1462
solution $x\con a'b\pmod{n}$ modulo~$n$. Thus, it is of interest to
1463
determine the units in $\zmod{n}$, i.e., the elements which have a
1464
multiplicative inverse.
1465
1466
We will use complete sets of residues\index{complete set of residues}
1467
to prove that the units in $\zmod{n}$ are exactly the~$a\in\zmod{n}$
1468
such that $\gcd(\tilde{a},n)=1$ for any lift $\tilde{a}$ of~$a$
1469
to~$\Z$ (it doesn't matter which lift).
1470
1471
\begin{definition}[Complete Set of Residues]
1472
We call a subset $R\subset\Z$ of size~$n$ whose reductions modulo~$n$ are
1473
pairwise distinct a \defn{complete set of residues}
1474
modulo~$n$. In other words, a complete set of residues is a choice of
1475
representative for each equivalence class in $\zmod{n}$.
1476
\end{definition}
1477
For example,
1478
$$
1479
R=\{0,1,2,\ldots,n-1\}
1480
$$
1481
is a complete set of residues modulo~$n$.
1482
When $n=5$,
1483
$R = \{0,1,-1,2,-2\}$
1484
is a complete set of residues.
1485
1486
\begin{lemma}\label{lem:residues}
1487
If~$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\}$
1489
is also a complete set of residues modulo~$n$.
1490
\end{lemma}
1491
\begin{proof}
1492
If $ax\con ax'\pmod{n}$ with $x, x'\in R$, then
1493
Proposition~\ref{prop:cancel} implies that $x\con{}x'\pmod{n}$.
1494
Because $R$ is a complete set of residues, this implies
1495
that $x=x'$. Thus the elements of
1496
$aR$ have distinct reductions modulo~$n$.
1497
It follows, since $\#aR=n$, that $aR$ is a
1498
complete set of residues modulo~$n$.
1499
\end{proof}
1500
1501
\begin{proposition}[Units]\label{prop:unitsmodn}\iprop{units}
1502
If $\gcd(a,n)=1$, then the equation
1503
$
1504
ax\con b\pmod{n}
1505
$
1506
has a solution, and that solution is unique modulo~$n$.
1507
\end{proposition}
1508
\begin{proof}
1509
Let~$R$ be a complete set of residues modulo~$n$, so there
1510
is a unique element of~$R$ that is congruent to~$b$ modulo~$n$.
1511
By Lemma~\ref{lem:residues},
1512
$aR$ is also a complete set of residues modulo~$n$, so
1513
there is a unique element $ax\in aR$ that is congruent
1514
to~$b$ modulo~$n$, and we have $ax\con b\pmod{n}$.
1515
\end{proof}
1516
Algebraically, this proposition asserts that if $\gcd(a,n)=1$, then
1517
the map $\zmod{n}\ra \zmod{n}$ given by left multiplication by~$a$ is
1518
a bijection.
1519
1520
\begin{example}
1521
Consider the equation $2x\con 3\pmod{7}$,
1522
and the complete set $R = \{0,1,2,3,4,5,6\}$
1523
of coset representatives. We have
1524
$$
1525
2R = \{0,2,4,6,8\con 1, 10\con 3, 12\con 5\},
1526
$$
1527
so $2\cdot 5\con 3\pmod{7}$.
1528
\end{example}
1529
1530
When $\gcd(a,n)\neq 1$, then the equation $ax\con b\pmod{n}$ may or
1531
may not have a solution. For example, $2x\con 1\pmod{4}$ has no
1532
solution, but $2x\con 2\pmod{4}$ does, and in fact it has more than
1533
one mod~$4$ ($x=1$ and $x=3$). Generalizing
1534
Proposition~\ref{prop:unitsmodn}, we obtain the following more general
1535
criterion for solvability.
1536
\begin{proposition}[Solvability]\label{prop:cancel2}\iprop{solvability}
1537
The equation $ax\con b\pmod{n}$ has a solution
1538
if 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
1554
In Chapter~\ref{ch:reciprocity} we will study quadratic reciprocity,
1555
which gives a nice criterion for whether or not a quadratic equation
1556
modulo~$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}%
1562
The group of units $(\zmod{n})^*$ of the ring $\zmod{n}$ will
1563
be of great interest to us. Each element of
1564
this group has an order, and Lagrange's theorem from group theory
1565
implies that each element of $(\zmod{n})^*$ has order that divides
1566
the order of $(\zmod{n})^*$. In elementary number theory this
1567
fact goes by the monicker ``Fermat's Little Theorem'', and we
1568
reprove 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}
1572
Let $n\in\N$ and $x\in\Z$ and suppose that $\gcd(x,n)=1$.
1573
The \defn{order} of $x$ modulo~$n$ is the smallest $m\in\N$
1574
such that
1575
$$
1576
x^m \con 1\pmod{n}.
1577
$$
1578
\end{definition}
1579
To show that the definition makes sense, we verify
1580
that such an~$m$ exists. Consider $x, x^2, x^3, \ldots$ modulo~$n$.
1581
There are only finitely many residue classes modulo~$n$, so we must
1582
eventually find two integers $i, j$ with $i<j$ such that
1583
$$
1584
x^j\con x^i\pmod{n}.
1585
$$
1586
Since $\gcd(x,n)=1$, Proposition~\ref{prop:cancel} implies that
1587
we 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}
1594
For $n\in\N$, let
1595
$$
1596
\vphi(n) = \#\{a \in \N : a \leq n \text{ and } \gcd(a,n)=1\}.
1597
$$
1598
\end{definition}
1599
For 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*}
1606
Also, if~$p$ is any prime number then
1607
$$
1608
\vphi(p) = \#\{1,2,\ldots,p-1\} = p-1.
1609
$$
1610
In Section~\ref{sec:multi_funcs}, we will prove that~$\vphi$ is a
1611
multiplicative 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}
1616
If $\gcd(x,n)=1$, then
1617
$$
1618
x^{\vphi(n)} \con 1\pmod{n}.
1619
$$
1620
\end{theorem}
1621
\begin{proof}
1622
As mentioned above, Fermat's Little Theorem has the following group-theoretic
1623
\index{Fermat's little theorem!group-theoretic interpretation}
1624
interpretation. 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
$$
1630
which has order~$\vphi(n)$. The theorem then asserts
1631
that 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
1633
general 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
1636
We 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
$$
1640
In the same way that we proved Lemma~\ref{lem:residues},
1641
we see that the reductions modulo~$n$ of the elements of $xP$
1642
are the same as the reductions of the elements of $P$.
1643
Thus
1644
$$
1645
\prod_{a\in P} (xa) \con \prod_{a \in P} a \pmod{n},
1646
$$
1647
since the products are over the same numbers modulo~$n$.
1648
Now cancel the $a$'s on both sides to get
1649
$$x^{\#P} \con 1\pmod{n},$$
1650
as claimed.
1651
\end{proof}
1652
1653
1654
1655
\subsection{Wilson's Theorem}\index{Wilson's theorem}\index{theorem!of Wilson}
1656
The following characterization of prime numbers, from the 1770s, is
1657
called ``Wilson's Theorem'', though it was first proved by
1658
Lagrange\index{Lagrange}.
1659
\begin{proposition}[Wilson's Theorem]\label{prop:wilson}\iprop{Wilson}
1660
An integer $p>1$ is prime if and only if
1661
$(p-1)! \con -1 \pmod{p}.$
1662
\end{proposition}
1663
For example,
1664
if $p=3$, then $(p-1)! = 2\con -1\pmod{3}$.
1665
If $p=17$, then
1666
$$(p-1)! = 20922789888000 \con -1\pmod{17}.$$
1667
But if $p=15$, then
1668
$$(p-1)! = 87178291200 \con 0 \pmod{15},$$
1669
so $15$ is composite. Thus Wilson's theorem could be viewed
1670
as a primality test, though, from a computational point of view,
1671
it is probably the {\em least efficient}
1672
primality test since computing $(n-1)!$ takes so many steps.
1673
\begin{proof}
1674
The statement is clear when $p=2$, so henceforth we assume
1675
that $p>2$.
1676
We 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
1678
the equation
1679
$$
1680
ax\con 1\pmod{p}
1681
$$
1682
has a unique solution $a'\in\{1,2,\ldots,p-1\}$.
1683
If $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\}$.
1686
We can thus pair off the elements of
1687
$\{2,3,\ldots,p-2\}$,
1688
each with their inverse.
1689
Thus
1690
$$
1691
2\cdot 3 \cdot \cdots \cdot (p-2) \con 1\pmod{p}.
1692
$$
1693
Multiplying both sides by $p-1$ proves that
1694
$(p-1)! \con -1\pmod{p}$.
1695
1696
Next we assume that $(p-1)! \con -1\pmod{p}$ and
1697
prove that~$p$ must be prime. Suppose not, so that~$p\geq 4$
1698
is a composite number. Let~$\ell$ be a prime divisor
1699
of~$p$. Then $\ell<p$, so $\ell\mid (p-1)!$. Also,
1700
by assumption,
1701
$$
1702
\ell \mid p \mid ((p-1)! + 1).
1703
$$
1704
This is a contradiction, because a prime can not divide a number~$a$ and
1705
also divide $a+1$, since it would then have to divide $(a+1) - a=1$.
1706
\end{proof}
1707
1708
\begin{example}
1709
We illustrate the key step in the above proof in the case $p=17$.
1710
We have
1711
$$
1712
2\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},$$
1716
where we have paired up the numbers $a, b$ for
1717
which $ab\con 1\pmod{17}$.
1718
\end{example}
1719
1720
\section{The Chinese Remainder Theorem}\label{sec:chinese}%
1721
\index{Chinese remainder theorem}
1722
In this section we prove the Chinese Remainder Theorem, which gives
1723
conditions under which a system of linear equations is guaranteed to
1724
have a solution.
1725
In the 4th century a Chinese mathematician asked the following:
1726
\begin{question}\label{q:chinese}
1727
There is a quantity whose number is unknown. Repeatedly divided
1728
by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the
1729
remainder is 2. What is the quantity?
1730
\end{question}
1731
In modern notation, Question~\ref{q:chinese} asks us to
1732
find a positive integer solution to the following system of
1733
three equations:
1734
\begin{align*}
1735
x &\con 2 \pmod{3}\\
1736
x &\con 3 \pmod{5}\\
1737
x &\con 2 \pmod{7}
1738
\end{align*}
1739
The Chinese Remainder Theorem asserts that a solution
1740
exists, 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}
1746
Let $a, b\in\Z$ and $n,m\in\N$ such that
1747
$\gcd(n,m)=1$. Then there exists $x\in\Z$ such that
1748
\begin{align*}
1749
x&\con a\pmod{m},\\
1750
x&\con b\pmod{n}.
1751
\end{align*}
1752
Moreover~$x$ is unique modulo~$mn$.
1753
\end{theorem}
1754
\begin{proof}
1755
If we can solve for~$t$ in the equation
1756
$$
1757
a+tm \con b \pmod{n},
1758
$$
1759
then $x=a+tm$ will satisfy both congruences.
1760
To see that we can solve, subtract~$a$ from
1761
both sides and use Proposition~\ref{prop:unitsmodn}
1762
together with our assumption that $\gcd(n,m)=1$ to see that
1763
there is a solution.
1764
1765
For 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
1767
z$ 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}
1778
Given coprime integers $m$ and $n$ and integers $a$ and $b$,
1779
this algorithm find an integer $x$ such that $x\con a\pmod{m}$
1780
and $x\con b\pmod{n}$.
1781
\begin{steps}
1782
\item{}[Extended GCD] Use Algorithm~\ref{alg:xgcd} below
1783
to 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}
1788
Since $c\in\Z$, we have $x\con a\pmod{m}$,
1789
and using that $cm+dn=1$, we have
1790
$a + (b-a)cm \con a + (b-a) \con b\pmod{n}$.
1791
\end{proof}
1792
1793
Now we can answer Question~\ref{q:chinese}.
1794
First, we use Theorem~\ref{thm:crt}
1795
to find a solution to the pair of equations
1796
\begin{align*}
1797
x &\con 2 \pmod{3},\\
1798
x &\con 3 \pmod{5}.
1799
\end{align*}
1800
Set $a=2$, $b=3$, $m=3$, $n=5$.
1801
Step 1 is to find a solution to $t\cdot 3 \con 3-2\pmod{5}$.
1802
A solution is $t=2$. Then $x=a+tm=2+2\cdot 3 = 8$.
1803
Since any~$x'$ with $x'\con x\pmod{15}$ is also a solution to
1804
those two equations, we can solve all three equations by
1805
finding a solution to the pair of equations
1806
\begin{align*}
1807
x &\con 8 \pmod{15}\\
1808
x &\con 2 \pmod{7}.
1809
\end{align*}
1810
Again, we find a solution to $t\cdot 15 \con 2-8\pmod{7}$.
1811
A solution is $t = 1$, so
1812
$$x=a+tm=8+15=23.$$
1813
Note that there are other solutions. Any $x'\con x\pmod{3\cdot 5\cdot 7}$
1814
is 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]
1819
A 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}
1825
Recall from Definition~\ref{def:phi}
1826
that 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}
1832
Suppose that $m,n\in\N$ and $\gcd(m,n)=1$.
1833
Then the map
1834
\begin{equation}\label{eqn:crtprod}
1835
\psi: (\zmod{mn})^* \ra (\zmod{m})^* \cross (\zmod{n})^*.
1836
\end{equation}
1837
defined by
1838
$$
1839
\psi(c) = (c\text{ mod } m, \,\,c \text{ mod }n)
1840
$$
1841
is a bijection.
1842
\end{lemma}
1843
\begin{proof}
1844
We 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$.
1846
Thus $c=c'$ as elements of $(\zmod{mn})^*$.
1847
1848
Next we show that~$\psi$ is surjective. Given~$a$ and~$b$
1849
with $\gcd(a,m)=1$ and
1850
$\gcd(b,n)=1$, Theorem~\ref{thm:crt} implies that there
1851
exists~$c$ with $c\con a\pmod{m}$ and $c\con b\pmod{n}$. We
1852
may 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}
1857
The 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
1873
The proposition is helpful in computing $\vphi(n)$, at least
1874
if we assume we can compute the factorization of~$n$ (see
1875
Section~\ref{sec:phin} for a connection between factoring $n$
1876
and computing $\vphi(n)$).
1877
For example,
1878
$$
1879
\vphi(12) = \vphi(2^2)\cdot \vphi(3) = 2\cdot 2 = 4.
1880
$$
1881
Also, 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$
1886
minus the number of those that are divisible by $p$.
1887
Thus, 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}
1894
This section is about how to solve the equation $ax\con 1\pmod{n}$
1895
when we know it has a solution, and how to efficiently compute
1896
$a^m\pmod{n}$. We also discuss a simple probabilistic primality
1897
test\index{primality test!probabilistic} that relies on our ability to
1898
compute $a^m\pmod{n}$ quickly. All three of these algorithms are of
1899
fundamental importance to the cryptography algorithms of
1900
Chapter~\ref{ch:crypto}.
1901
1902
1903
\subsection{How to Solve $ax\con 1\pmod{n}$}
1904
Suppose $a, n\in\N$ with $\gcd(a,n)=1$. Then
1905
by Proposition~\ref{prop:unitsmodn}
1906
the equation $ax\con 1\pmod{n}$ has a unique solution.
1907
How can we find it?
1908
1909
\begin{proposition}[Extended Euclidean representation]
1910
\label{prop:xgcd}\iprop{extended Euclidean}
1911
Suppose $a,b\in\Z$ and let $g=\gcd(a,b)$. Then
1912
there exists $x,y\in\Z$ such that
1913
$$
1914
ax + by = g.
1915
$$
1916
\end{proposition}
1917
\begin{remark}
1918
If $e=cg$ is a multiple of~$g$, then
1919
$cax + cby = cg = e,$ so $e = (cx)a+(cy)b$ can
1920
also 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}
1929
has a solution $x\in\Z$. Multiplying (\ref{eqn:xgcd}) through by~$g$
1930
yields $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
1934
Given $a,b$ and $g=\gcd(a,b)$, our proof of
1935
Proposition~\ref{prop:xgcd} gives a way to explicitly find $x,y$ such
1936
that $ax+by=g$, assuming one knows an algorithm to solve linear
1937
equations modulo~$n$. Since we do not know such an algorithm, we now
1938
discuss a way to explicitly find~$x$ and~$y$. This algorithm
1939
will 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
1941
find~$x$ and~$y$ such that $ax+ny = 1$. Then $ax\con 1\pmod{n}.$
1942
1943
Suppose $a=5$ and $b=7$. The steps of Algorithm~\ref{alg:gcd} to
1944
compute $\gcd(5,7)$ are, as follows. Here we underlying, because it
1945
clarifies the subsequent back substitution we will use to find~$x$
1946
and~$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*}
1951
On the right, we have back-substituted in order to write each partial
1952
remainder as a linear combination of~$a$ and~$b$. In the last step,
1953
we obtain $\gcd(a,b)$ as a linear combination of~$a$ and~$b$, as
1954
desired.
1955
1956
That example was not too complicated, so we try another one.
1957
Let $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*}
1965
Thus $x=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}
1969
Suppose $a$ and $b$ are integers and let $g=\gcd(a,b)$.
1970
This algorithm finds~$d$, $x$ and $y$ such that $ax+by = g$.
1971
We describe only the steps when $a>b\geq 0$, since one
1972
can 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]
1977
Use Algorithm~\ref{alg:division} to write $a = qb + c$ with $0\leq c<b$.
1978
\item{} [Shift]
1979
Set $(a, b, r, s, x, y) \assign (b, c, x-qr, y-qs, r, s)$
1980
and go to step~\ref{alg:xgcd_2}.
1981
\end{steps}
1982
\end{algorithm}
1983
\begin{proof}
1984
This algorithm is the same as Algorithm~\ref{alg:gcd}, except that we
1985
keep track of extra variables $x,y,r,s$, so it terminates and when
1986
it terminates $d=\gcd(a,b)$.
1987
We omit the rest of the inductive proof that the algorithm
1988
is correct, and instead refer the reader to
1989
\cite[\S1.2.1]{knuth1} which contains a detailed proof
1990
in the context of a discussion of how one
1991
writes mathematical proofs.
1992
\end{proof}
1993
1994
\begin{algorithm}{Inverse Modulo $n$}\label{alg:inversemod}
1995
Suppose $a$ and $n$ are integers and $\gcd(a,n)=1$.
1996
This 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
1999
integers $x,y$ such that $ax+ny=\gcd(a,n)=1$.
2000
\item{} [Finished] Output $x$.
2001
\end{steps}
2002
\end{algorithm}
2003
\begin{proof}
2004
Reduce $ax+ny=1$ modulo~$n$ to see that $x$
2005
satisfies $ax\con 1\pmod{n}$.
2006
\end{proof}
2007
See Section~\ref{sec:comp_lin_eq} for implementations
2008
of Algorithms~\ref{alg:xgcd} and \ref{alg:inversemod}.
2009
2010
\begin{example}
2011
Solve $17x \con 1\pmod{61}$.
2012
First, 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*}
2020
Thus $17\cdot 18 + 61\cdot (-5) = 1$ so $x=18$
2021
is 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}
2028
Let~$a$ and~$n$ be integers, and~$m$ a nonnegative integer.
2029
In this section we describe an efficient algorithm to compute
2030
$a^m\pmod{n}$. For the cryptography
2031
applications in Chapter~\ref{ch:crypto},~$m$ will have
2032
hundreds of digits.
2033
2034
The 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
2036
reducing modulo~$m$. Note that after each arithmetic operation is
2037
completed, we reduce the result modulo~$n$ so that the sizes of the
2038
numbers involved do not get too large. Nonetheless, this algorithm is
2039
horribly inefficient because it takes $m-1$ multiplications, which
2040
is huge if~$m$ has hundreds of digits.
2041
2042
A much more efficient algorithm for computing $a^m\pmod{n}$ involves
2043
writing~$m$ in binary, then expressing $a^m$ as a product of
2044
expressions $a^{2^i}$, for various~$i$. These latter expressions can
2045
be computed by repeatedly squaring $a^{2^i}$. This more clever algorithm
2046
is not ``simpler'', but it is vastly more efficient since the number
2047
of operations needed grows with the number of binary digits of~$m$, whereas
2048
with 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}
2052
Let $m$ be a nonnegative integer. This algorithm writes~$m$ in
2053
binary, 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]
2059
If~$m$ is odd, set $\eps_i\assign 1$, otherwise $\eps_i\assign 0$.
2060
Increment~$i$.
2061
\item{}[Divide by $2$]
2062
Set~$m \assign \left\lfloor\frac{m}{2}\right\rfloor$, the
2063
greatest 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}
2068
Let~$a$ and~$n$ be integers and~$m$ a nonnegative integer.
2069
This 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
2077
to $a^{2^r}$, where $r+1$ is the number of binary
2078
digits of~$m$.
2079
\item{}[Multiply Powers] Multiply together the
2080
$a^{2^i}$ such that $\eps_i=1$,
2081
always working modulo~$n$.
2082
\end{steps}
2083
\end{algorithm}
2084
See Section~\ref{sec:comp_powermod} for
2085
an implementation of Algorithms~\ref{alg:binary} and \ref{alg:power}.
2086
2087
2088
2089
We can compute the last~$2$ digits of $6^{91}$, by
2090
finding $6^{91}\pmod{100}$. Make a table whose first column, labeled~$i$,
2091
contains~$0$,~$1$,~$2$, etc. The second column, labeled~$m$, is got
2092
by dividing the entry above it by~$2$ and taking the integer part of
2093
the result. The third column, labeled $\eps_i$, records whether or
2094
not the second column is odd. The fourth column is computed by
2095
squaring, 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
2101
0 & 91 & 1 & 6 \\\hline
2102
1 & 45 & 1 & 36\\\hline
2103
2 & 22 & 0 & 96\\\hline
2104
3 & 11 & 1 & 16\\\hline
2105
4 & 5 & 1 & 56\\\hline
2106
5 & 2 & 0 & 36\\\hline
2107
6 & 1 & 1 & 96\\\hline
2108
\end{tabular}
2109
\end{center}
2110
We 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
$$
2116
That is easier than multiplying~$6$ by itself $91$ times.
2117
2118
\begin{remark}
2119
Alternatively, we could simplify the computation using
2120
Theorem~\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$,
2123
we 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}
2131
An integer~$p>1$ is prime if and only if
2132
for {\em every} $a\not\con 0\pmod{p}$,
2133
$$
2134
a^{p-1}\con 1\pmod{p}.
2135
$$
2136
\end{theorem}
2137
\begin{proof}
2138
If~$p$ is prime, then the statement follows from
2139
Proposition~\ref{prop:wilson}. If~$p$ is composite,
2140
then there is a divisor~$a$ of~$p$ with $a\neq 1,p$.
2141
If $a^{p-1}\con 1\pmod{p}$, then $p\mid a^{p-1} -1$.
2142
Since $a\mid p$, we have $a \mid a^{p-1} -1$ hence
2143
$a\mid 1$, a contradiction.
2144
\end{proof}
2145
Suppose $n\in\N$. Using this theorem and Algorithm~\ref{alg:power}, we
2146
can either quickly prove that~$n$ is not prime, or convince ourselves
2147
that~$n$ is likely prime (but not quickly prove that~$n$ is prime).
2148
For example, if $2^{n-1}\not\con 1\pmod{n}$, then we have proved
2149
that~$n$ is not prime. On the other hand, if $a^{n-1}\con 1\pmod{n}$
2150
for a few~$a$, it ``seems likely'' that~$n$ is prime, and we loosely
2151
refer to such a number that seems prime for several bases as a
2152
\defn{pseudoprime}.
2153
2154
There are composite numbers~$n$ (called \defn{Carmichael numbers})
2155
with the amazing property that
2156
$a^{n-1}\con 1\pmod{n}$ for {\em all} $a$ with $\gcd(a,n)=1$. The
2157
first Carmichael number is $561$, and it is a theorem that there
2158
are infinitely many such numbers (\cite{carmichael}).
2159
2160
\begin{example}
2161
Is~$p=323$ prime?
2162
We compute $2^{322}\pmod{323}$.
2163
Making 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
2168
0 & 322 & 0 & 2 \\\hline
2169
1 & 161 & 1 & 4 \\\hline
2170
2 & 80 & 0 & 16 \\\hline
2171
3 & 40 & 0 & 256 \\\hline
2172
4 & 20 & 0 & 290 \\\hline
2173
5 & 10 & 0 & 120 \\\hline
2174
6 & 5 & 1 & 188 \\\hline
2175
7 & 2 & 0 & 137 \\\hline
2176
8 & 1 & 1 & 35 \\\hline
2177
\end{tabular}
2178
\end{center}
2179
Thus
2180
$$2^{322} \con 4\cdot 188\cdot 35 \con 157\pmod{323},$$
2181
so $323$ is not prime, though this computation gives no information
2182
about $323$ factors as a product of primes.
2183
In fact, one finds that $323 = 17\cdot 19$.
2184
\end{example}
2185
2186
It's possible to easily prove that a large number is composite, but the
2187
proof does not easily yield a factorization. For example if
2188
$$
2189
n = 95468093486093450983409583409850934850938459083,
2190
$$
2191
then $2^{n-1}\not\con 1\pmod{n}$, so~$n$ is composite.
2192
2193
Another practical primality test is the Miller-Rabin test,\index{primality test!Miller-Rabin} which has
2194
the property that each time it is run on a number~$n$ it either
2195
correctly asserts that the number is definitely not prime, or that it is
2196
probably prime, and the probability of correctness goes up with each
2197
successive call. For a precise statement and implementation
2198
of Miller-Rabin, along with proof of correctness, see
2199
Section~\ref{sec:comp_primality}.
2200
If Miller-Rabin is called~$m$ times on~$n$ and in
2201
each case claims that~$n$ is probably prime, then
2202
one can in a precise sense bound the probability
2203
that~$n$ is composite in terms of~$m$.
2204
For 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,
2212
Until recently it was an open problem to give an algorithm (with proof)
2213
that decides whether or not any integer is prime in time bounded by a
2214
polynomial in the number of digits of the integer. Agrawal, Kayal,
2215
and Saxena recently found the first polynomial-time primality test
2216
(see \cite{agrawal:primes}). We will not discuss their algorithm
2217
further, because for our applications to cryptography Miller-Rabin
2218
or pseudoprimality tests will be sufficient.
2219
2220
2221
\section{The Structure of $(\zmod{p})^*$}
2222
\label{sec:primitive}
2223
This section is about the structure of the group $(\zmod{p})^*$ of
2224
units modulo a prime number~$p$.\index{units!of $\zmod{p}$ are cyclic|nn}
2225
The main result is that this group is always cyclic.
2226
We will use this result later in Chapter~\ref{ch:reciprocity}
2227
in our proof of quadratic reciprocity.
2228
2229
\begin{definition}[Primitive root]\label{defn:primroot}
2230
A \defn{primitive root} modulo an integer~$n$ is an element of
2231
$(\zmod{n})^*$ of order $\vphi(n)$.
2232
\end{definition}
2233
We will prove that there is a primitive root modulo every
2234
prime~$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,
2237
since it completely determines the structure of $(\zmod{p})^*$ as an
2238
abelian group.
2239
2240
If~$n$ is an odd prime power, then there is a primitive root
2241
modulo~$n$ (see \exref{ch:cong}{ex:prim2}), but there is no primitive root
2242
modulo 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
2246
Section~\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$
2248
there are exactly~$d$ elements of $(\zmod{p})^*$ whose order divides~$d$.
2249
We then use this result in Section~\ref{sec:struc_zp} to produce an
2250
element of $(\zmod{p})^*$ of order~$q^r$ when~$q^r$ is a prime power that
2251
exactly divides $p-1$ (i.e., $q^r$ divides $p-1$, but $q^{r+1}$ does not
2252
divide $p-1$), and multiply together these elements to obtain an element
2253
of $(\zmod{p})^*$ of order $p-1$.
2254
2255
\subsection{Polynomials over $\zmod{p}$}\label{sec:polys_zp}
2256
\index{polynomials!over $\zmod{p}$}
2257
2258
The polynomials $x^2-1$ has four roots in $\zmod{8}$, namely
2259
$1$, $3$, $5$, and $7$. In contrast, the following proposition
2260
shows that a polynomial of degree~$d$ over a field,
2261
such as $\zmod{p}$, can have at most $d$ roots.
2262
\begin{proposition}[Root Bound]\label{prop:atmost}
2263
\iprop{root bound}
2264
Let $f\in k[x]$ be a nonzero polynomial
2265
over 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}
2269
We prove the proposition by induction on $\deg(f)$. The cases in
2270
which
2271
$\deg(f)\leq 1$ are clear. Write
2272
$f = a_n x^n + \cdots a_1 x + a_0$. If
2273
$f(\alpha)=0$ then
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*}
2280
for some polynomial $g(x)\in k[x]$.
2281
Next suppose that $f(\beta)=0$ with $\beta\neq \alpha$. Then
2282
$(\beta-\alpha) g(\beta) = 0$, so, since $\beta-\alpha\neq 0$,
2283
we have $g(\beta)=0$.
2284
By our inductive hypothesis,~$g$ has at most $n-1$ roots, so
2285
there are at most $n-1$ possibilities for~$\beta$.
2286
It follows that~$f$ has at most~$n$ roots.
2287
\end{proof}
2288
2289
\begin{proposition}\label{prop:dsols}
2290
Let~$p$ be a prime number and let~$d$ be a divisor
2291
of $p-1$. Then $f = x^d-1\in(\zmod{p})[x]$ has
2292
exactly~$d$ roots in $\zmod{p}$.
2293
\end{proposition}
2294
\begin{proof}
2295
Let $e=(p-1)/d$. We have
2296
\begin{align*}
2297
x^{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*}
2301
where $g\in (\zmod{p})[x]$ and
2302
$\deg(g) = de-d = p-1-d$.
2303
Theorem~\ref{thm:fermatlittle}
2304
implies that $x^{p-1}-1$ has
2305
exactly $p-1$ roots in $\zmod{p}$, since every nonzero element of
2306
$\zmod{p}$ is a root! By Proposition~\ref{prop:atmost},~$g$
2307
has {\em at most} $p-1-d$ roots and $x^d-1$ has at most~$d$ roots.
2308
Since a root of $(x^d-1)g(x)$ is a root of either $x^d-1$ or $g(x)$
2309
and $x^{p-1}-1$ has $p-1$ roots,~$g$ must have exactly $p-1-d$ roots
2310
and $x^d-1$ must have exactly~$d$ roots, as claimed.
2311
\end{proof}
2312
2313
We pause to reemphasize that the analogue of
2314
Proposition~\ref{prop:dsols} is false when~$p$ is replaced by a
2315
composite integer~$n$, since a root mod~$n$ of a product of two
2316
polynomials need not be a root of either factor.
2317
For example, $f = x^2-1\in \zmod{15}[x]$ has
2318
the four roots $1$, $4$, $11$, and $14$.
2319
2320
2321
\subsection{Existence of Primitive Roots}\label{sec:struc_zp}%
2322
\index{primitive root!existence}
2323
Recall from Section~\ref{sec:flittle} that the \defn{order} of an
2324
element $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
2326
using the results of Section~\ref{sec:polys_zp} to produce an element
2327
of $(\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
2329
order $p-1$.
2330
2331
We will use the following lemma to assemble elements of
2332
each order dividing $p-1$ to produce an
2333
element 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}
2339
This is a general fact about commuting elements of any group; our proof
2340
only uses that $ab=ba$ and nothing special about $(\zmod{n})^*$. Since
2341
$$
2342
(ab)^{rs} = a^{rs}b^{rs}=1,
2343
$$
2344
the order of $ab$ is a divisor of $rs$.
2345
Write this divisor as $r_1 s_1$ where $r_1\mid r$
2346
and $s_1\mid s$.
2347
Raise both sides of the equation
2348
$$
2349
a^{r_1 s_1}b^{r_1 s_1} = (ab)^{r_1 s_1} = 1.
2350
$$
2351
to the power $r_2 = r/r_1$ to obtain<