forked from williamstein/ent
-
Notifications
You must be signed in to change notification settings - Fork 0
/
body.tex
8939 lines (8108 loc) · 324 KB
/
body.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter*{Preface}
\markboth{Preface}{Preface}
\addcontentsline{toc}{chapter}{\numberline{}Preface}
This is a book about prime numbers, congruences, secret messages, and
elliptic curves that you can read cover to cover. It grew out of
undergraduate courses that the author taught at Harvard, UC San Diego,
and the University of Washington.
The systematic study of number theory was initiated around 300{\sc B.C.} when
Euclid proved that there are infinitely many prime numbers, and also
cleverly deduced the fundamental theorem of arithmetic, which asserts
that every positive integer factors uniquely as a product of primes.
Over a thousand years later (around 972{\sc A.D.}) Arab mathematicians
formulated the {\em congruent number problem} that asks for a way to
decide whether or not a given positive integer $n$ is the area of a
right triangle, all three of whose sides are rational numbers. Then
another thousand years later (in 1976), Diffie and Hellman introduced the
first ever public-key cryptosystem, which enabled two people to
communicate secretely over a public communications channel with no
predetermined secret; this invention and the ones that followed it
revolutionized the world of digital communication. In the 1980s and
1990s, elliptic curves revolutionized number theory, providing
striking new insights into the congruent number problem, primality
testing, public-key cryptography, attacks on public-key systems, and
playing a central role in Andrew Wiles' resolution of Fermat's Last
Theorem.
Today, pure and applied number theory is an exciting mix of
simultaneously broad and deep theory, which is constantly informed and
motivated by algorithms and explicit computation. Active research is
underway that promises to resolve the congruent number problem, deepen
our understanding into the structure of prime numbers, and both
challenge and improve our ability to communicate securely. The goal
of this book is to bring the reader closer to this world.
The reader is strongly encouraged to do every exercise in this book,
checking their answers in the back (where many, but not all, solutions
are given). Also, throughout the text there, are examples of
calculations done using the powerful free open source mathematical
software system Sage (\url{http://www.sagemath.org}), and the reader
should try every such example and experiment with similar examples.
\vspace{1.5ex}\noindent{}{\bf Background.} The reader should know how
to read and write mathematical proofs and must know the basics of
groups, rings, and fields. Thus, the prerequisites for this book are
more than the prerequisites for most elementary number theory books,
while still being aimed at undergraduates.
\vspace{1.5ex}\noindent{}{\bf Notation and Conventions.} We let
$\N=\{1,2,3,\ldots\}$ denote the natural numbers, and use the standard
notation $\Z$, $\Q$, $\R$, and $\C$ for the rings of integer,
rational, real, and complex numbers, respectively.\index{notation} In
this book, we will use the words proposition, theorem, lemma, and
corollary as follows. Usually a proposition is a less important or
less fundamental assertion, a theorem is a deeper culmination of ideas, a
lemma is something that we will use later in this book to prove a
proposition or theorem, and a corollary is an easy consequence of a
proposition, theorem, or lemma. More difficult exercises are marked
with a (*).
\vspace{1.5ex}\noindent{}{\bf Acknowledgements.} I would like to thank
Brian Conrad, Carl Pomerance, and Ken Ribet for many clarifying
comments and suggestions. Baurzhan Bektemirov, Lawrence
Cabusora, and Keith Conrad read drafts of this book and made many
comments, and Carl Witty commented extensively on the first two
chapters. Frank Calegari used the course when teaching Math 124 at
Harvard, and he and his students provided much feedback. Noam Elkies
made comments and suggested \exref{ch:reciprocity}{ex:rec8}. Seth
Kleinerman wrote a version of Section~\ref{sec:contfrac_e} as a class
project. Hendrik Lenstra made helpful remarks about how to present
his factorization algorithm. Michael Abshoff, Sabmit Dasgupta, David
Joyner, Arthur Patterson, George Stephanides, Kevin Stern, Eve
Thompson, Ting-You Wang, and Heidi Williams all suggested corrections.
I also benefited from conversations with Henry Cohn and David Savitt.
I used \sage (\cite{sage}), emacs, and \LaTeX{} in the preparation of
this book.
% Stephanides of University of Macedonia
%Heidi.L.Williams@Dartmouth.EDU
\cleardoublepage
\pagenumbering{arabic}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Chapter: Prime Numbers
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Prime Numbers}
\label{ch:prime}
Every positive integer can be written uniquely as a product of prime
numbers, e.g., $100 = 2^2 \cdot 5^2$. This is surprisingly difficult
to prove, as we will see below. Even more astounding is that actually
{\em finding} a way to write certain 1,000-digit numbers as a product
of primes seems out of the reach of present technology, an observation
that is used by millions of people every day when they buy things
online.
Since prime numbers are the building blocks of integers, it is
natural to wonder how the primes are distributed among the integers.
\begin{quote}
``There are two facts about the distribution of prime numbers. The
first is that, [they are] the most arbitrary and ornery objects
studied by mathematicians: they grow like weeds among the natural
numbers, seeming to obey no other law than that of chance, and
nobody can predict where the next one will sprout. The second fact
is even more astonishing, for it states just the opposite: that the
prime numbers exhibit stunning regularity, that there are laws
governing their behavior, and that they obey these laws with almost
military precision.''\\\mbox{} \hspace{2in} --- Don Zagier \cite{zagier:primes50}
\end{quote}
The Riemann Hypothesis, which is the most famous unsolved problem in
number theory, postulates a very precise answer to the question of
how the prime numbers are distributed.
This chapter lays the foundations for our study of the theory of
numbers by weaving together the themes of prime numbers, integer
factorization, and the distribution of primes. In
Section~\ref{sec:fundamental_thm}, we rigorously prove that every
positive integer is a product of primes, and give examples of specific
integers for which finding such a decomposition would win one a large
cash bounty. In Section~\ref{sec:primeseq}, we discuss theorems about
the set of prime numbers\index{primes}, starting with
Euclid's\index{Euclid} proof that this set is infinite, and discuss the
largest known prime. Finally we discuss the distribution of primes
via the prime number theorem and the Riemann Hypothesis.
\section{Prime Factorization}
\label{sec:fundamental_thm}
\subsection{Primes}\label{sec:primes}
The set of {\em natural numbers}\index{natural numbers} is
$$
\N = \{1,2,3,4,\ldots\},
$$
and the set of {\em integers}\index{integers} is
$$
\Z = \{\ldots, -2, -1, 0, 1,2,\ldots\}.
$$
% \begin{remark}
% One reason the integers are denoted by~$\Z$ is because the German word
% for the integers is Zahlen\index{Zahlen}.
% \end{remark}
% The integers~$\Z$ are an example of a structure called a commutative ring.
% \begin{definition}[Commutative Ring]\label{defn:ring}
% A \defn{commutative ring} is a set~$R$ equipped with binary operations
% $+:R\times R \to R$ and $\times:R\times R \to R$ such that
% $(R,+)$ is an abelian group, $\times$ is associative and commutative,
% and for any $x,y,z\in R$ we have $x\times (y+z)=x\times y+x \times z$.
% We assume that $R$ contains an element $1$ such that $1x=x$ for
% all $x\in R$.
% \end{definition}
% The rational numbers, the real numbers, and the complex numbers are
% all also rings, but the set of natural numbers is not a ring, since
% $(\N,+)$ is not a group, e.g., because~$2$ does not have an additive
% inverse.
% We will not consider any non-commutative rings in this
% book, so the phrase ``let~$R$ be a ring'' will always mean that~$R$ is
% a commutative ring as defined above.
\begin{definition}[Divides]
If $a, b\in \Z$ we say that~$a$
\defn{divides}~$b$, written $a\mid b$, if $ac=b$ for some
$c\in \Z$. In this case, we say~$a$ is a \defn{divisor} of~$b$. We say
that~$a$ \defn{does not divide}~$b$, written $a\nmid b$, if there is no
$c\in \Z$ such that $ac=b$.
\end{definition}
For example, we have $2 \mid 6$ and $-3\mid 15$.
Also, all integers divide\index{divides}~$0$, and~$0$ divides
only~$0$. However, $3$ does not divide $7$ in $\Z$.
\begin{remark}
The notation $b \overset{\ds .}{:}\! a$ for ``$b$ is divisible by
$a$'' is common in Russian literature on number theory.
\end{remark}
% In order to formulate the definition of prime numbers, it will
% be useful to have the notion of unit.
% \begin{definition}[Unit]\label{defn:unit}
% A \defn{unit} is$
% that has a multiplicative inverse, i.e., for which there exists
% $y\in R$ such that $xy=1$.
% \end{definition}
% The units of the ring~$\Z$ of integers are $\pm 1$, since
% the inverses of all other (nonzero) integers are in $\Q$ and not in
% $\Z$.
% \begin{definition}[Irreducible]\label{defn:irred}
% Let $R$ be a ring and suppose $x\in R$ is not a unit. Then~$x$ is
% \defn{irreducible} if whenever $x=yz$ with $y,z\in R$, then~$y$
% or~$z$ is a unit.
% \end{definition}
% For example, the integer $2\in \Z$ is irreducible, because if $2=xy$,
% with $x,y\in\Z$, then one of $x$ or $y$ must be $\pm 1$ (there are
% just a few possibilities to check, since if $|x|>2$ or $|y|>2$, then
% $|xy| > 2$). The integer~$6$ is not irreducible because $6=2\cdot 3$,
% and neither~$2$ nor~$3$ is a unit.
% We introduce notion of ideal in order to define primality
% for elements of a ring.
% \begin{definition}[Ideal]\label{defn:ideal}
% A subset $I$ of a ring~$R$ is an \defn{ideal}
% if $I$ is closed under addition and if whenever
% $x\in R$ and $y\in I$, then $xy\in I$.
% \end{definition}
% For example, if $x$ is any element of $R$ then
% $$
% xR = (x) = \{xy: y \in R\}
% $$
% is easily seen to be an ideal because~$R$ is commutative.
% We call it the \defn{ideal generated by}~$x$.
% The sets $\{0\}$ and $R$ are also ideals of $R$,
% called the \defn{zero ideal} and \defn{unit ideal}, respectively.
% \begin{definition}[Prime Ideal]
% An ideal~$I\neq R$ of a ring $R$ is a \defn{prime ideal} if
% whenever $xy\in I$ then either $x\in I$ or $y\in I$.
% \end{definition}
% \begin{definition}[Prime Element]\label{defn:prime}
% An element~$x$ of a ring~$R$ is \defn{prime} if the ideal $xR$
% generated by~$x$ is prime.
% \end{definition}
% Unwinding the definitions, we see that an element $x\in R$ is prime if
% whenever $a, b\in R$ and $x\mid ab$, then $x\mid a$ or $x\mid b$.
\begin{definition}[Prime and Composite]\label{defn:prime_composite}
An integer $n>1$ is \defn{prime} if the only positive
divisors of $n$ are $1$ and~$n$.
We call~$n$ \defn{composite} if~$n$ is not prime.
\end{definition}
% Suppose $n>1$ is a natural number.
% Theorem~\ref{thm:euclid} below asserts that~$n$ is prime if and only
% if~$n$ is irreducible; equivalently,~$n$ is prime if and only if~$1$
% and~$n$ are the only positive divisors of~$n$.
The number~$1$ is neither prime nor composite. The first few
primes of~$\N$ are $$
2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, \ldots, $$
and the first few
composites are $$
4,6,8,9,10,12, 14, 15, 16, 18, 20, 21, 22, 24, 25,
26, 27, 28, 30, 32, 33, 34, \ldots. $$
\begin{remark}
J.\thinspace{}H. Conway argues in \cite[viii]{conway:sensual} that
$-1$ should be considered a prime, and in the 1914 table
\cite{lehmer:primetable}, Lehmer considers~$1$ to be a prime.
In this book, we consider neither $-1$ nor $1$ to be prime.
\end{remark}
\begin{sg}
We use \sage to compute all prime numbers between $a$ and $b-1$.
\begin{verbatim}
sage: prime_range(10,50)
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
\end{verbatim}
\noindent{}We can also compute the composites in an interval.
\begin{verbatim}
sage: [n for n in range(10,30) if not is_prime(n)]
[10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]
\end{verbatim}
\end{sg}
\noindent{}Every natural number is built, in a unique way, out of prime numbers:
\begin{theorem}[Fundamental Theorem of Arithmetic]\label{thm:fundamental}%
\index{fundamental theorem of arithmetic}%
\index{integers!factor uniquely}%
\ithm{unique factorization}%
Every natural number can be written as a product of primes
uniquely up to order.
\end{theorem}
Note that primes are the products with only one factor and~$1$ is the
empty product.
\begin{remark}
Theorem~\ref{thm:fundamental}, which we will prove in
Section~\ref{sec:proof_fundamental}, is trickier to prove than you
might first think. For example, unique factorization\index{unique
factorization} fails in the {\em ring}
$$
\Z[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b\in\Z\} \subset \C,
$$
where~$6$ factors in two different ways:
%into irreducible elements
$$
6 = 2\cdot 3 = (1+\sqrt{-5})\cdot (1-\sqrt{-5}).
$$
\end{remark}
\subsection{The Greatest Common Divisor}\index{greatest common divisor}
\index{gcd}
We will use the notion of the greatest common divisor of two integers to
prove that if~$p$ is a prime and $p\mid ab$, then $p\mid a$ or $p\mid
b$. Proving this is the key step in our proof of
Theorem~\ref{thm:fundamental}.
\begin{definition}[Greatest Common Divisor]
Let
$$
\gcd(a,b)=\max\left\{d\in \Z : d \mid a\text{ and } d\mid b\right\},
$$
unless both~$a$ and~$b$ are~$0$ in which case
$\gcd(0,0)=0$.
\end{definition}
For example,
$\gcd(1,2)=1$,
$\gcd(6,27)=3$, and
for any~$a$,
$\gcd(0,a)=\gcd(a,0)=a$.
If $a\neq 0$, the greatest common divisor exists because if $d\mid a$
then $d\leq |a|$, and there are only $|a|$ positive integers $\leq |a|$.
Similarly, the $\gcd$ exists when $b\neq 0$.
\begin{lemma}\label{lem:gcdprops}
For any integers $a$ and $b$, we have
$$
\gcd(a,b)= \gcd(b,a) = \gcd(\pm a, \pm b) = \gcd(a,b-a) = \gcd(a,b+a).
$$
\end{lemma}
\begin{proof}
We only prove that $\gcd(a,b) = \gcd(a,b-a)$, since the other cases
are proved in a similar way. Suppose $d\mid a$ and
$d\mid b$, so there exist integers $c_1$ and $c_2$ such that $dc_1 =
a$ and $dc_2 = b$. Then $b - a = dc_2 - dc_1 = d(c_2-c_1)$, so
$d\mid b-a$. Thus $\gcd(a,b)\leq \gcd(a,b-a)$, since the set over
which we are taking the max for $\gcd(a,b)$ is a subset of the set
for $\gcd(a,b-a)$. The same argument with $a$ replaced by $-a$
and $b$ replaced by $b-a$, shows that $\gcd(a,b-a)=\gcd(-a,b-a)\leq
\gcd(-a,b)=\gcd(a,b)$, which proves that $\gcd(a,b)=\gcd(a,b-a)$.
\end{proof}
\begin{lemma}\label{lem:gcdprops2}
Suppose $a,b,n\in\Z$. Then
$\gcd(a,b) = \gcd(a,b-an)$.
\end{lemma}
\begin{proof}
By repeated application of Lemma~\ref{lem:gcdprops}, we have
$$
\gcd(a,b) = \gcd(a,b-a) = \gcd(a,b-2a) = \cdots = \gcd(a,b-an).
$$
\end{proof}
Assume for the moment that we have already proved
Theorem~\ref{thm:fundamental}. A naive way to compute
$\gcd(a,b)$ is to factor~$a$ and~$b$ as a product of primes using
Theorem~\ref{thm:fundamental}; then the prime factorization of
$\gcd(a,b)$ can be read off from that of $a$ and $b$. For example, if
$a=2261$ and $b=1275$, then $a=7\cdot {\bf 17}\cdot 19$ and $b=3\cdot
5^2\cdot {\bf 17}$, so $\gcd(a,b) = 17$. It turns out that the
greatest common divisor of two integers, even huge numbers (millions
of digits), is surprisingly easy to compute using
Algorithm~\ref{alg:gcd} below, which computes $\gcd(a,b)$ without
factoring~$a$ or~$b$. \index{compute!greatest common divisor}
To motivate Algorithm~\ref{alg:gcd}, we compute $\gcd(2261,1275)$ in
a different way. First, we recall a helpful fact.
\begin{proposition}\label{prop:division}\iprop{long division}
Suppose that~$a$ and~$b$ are integers with $b\neq 0$. Then there
exists unique integers~$q$ and~$r$ such that $0\leq r< |b|$ and $a =
bq + r$.
\end{proposition}
\begin{proof}
For simplicity, assume that both~$a$ and~$b$ are positive (we leave
the general case to the reader). Let $Q$ be the set of all
nonnegative integers $n$ such that $a-bn$ is nonnegative. Then $Q$
is nonempty because $0\in Q$ and $Q$ is bounded because $a-bn<0$ for
all $n>a/b$. Let $q$ be the largest element of~$Q$. Then $r=a-bq <
b$, otherwise $q+1$ would also be in~$Q$. Thus~$q$ and~$r$ satisfy
the existence conclusion.
To prove uniqueness, suppose that $q'$ and $r'$ also satisfy the
conclusion. Then $q'\in Q$ since $r'=a-bq'\geq 0$, so $q'\leq q$,
and we can write $q'=q-m$ for some $m\geq 0$. If $q'\neq q$, then
$m\geq 1$ so $$r' = a-bq' = a-b(q-m) = a-bq + bm = r + bm \geq b$$ since
$r \geq 0$, a contradiction. Thus $q=q'$ and $r'=a-bq'=a-bq=r$, as
claimed.
\end{proof}
For us, an \defn{algorithm} is a finite sequence of instructions that
can be followed to perform a specific task, such as a sequence of
instructions in a computer program, which must terminate on
any valid input. The word ``algorithm'' is sometimes used more
loosely (and sometimes more precisely) than defined here, but this
definition will suffice for us.
\begin{algorithm}{Division Algorithm}\label{alg:division}%
\index{division algorithm}
Suppose $a$ and $b$ are integers with $b\neq 0$. This algorithm
computes integers $q$ and $r$ such that $0\leq r<|b|$ and
$a=bq+r$.
\end{algorithm}
We will not describe the actual steps of Algorithm~\ref{alg:division},
since it is just the familiar long division algorithm. Note that it
might not be exactly the same as the standard long division algorithm
you learned in school, because we make the remainder positive even
when dividing a negative number by a positive number.
We use the division algorithm repeatedly to compute
$\gcd(2261,1275)$. Dividing $2261$ by $1275$ we find that
$$
2261 = 1\cdot 1275 + 986,
$$
so $q=1$ and $r=986$.
Notice that if a natural number~$d$ divides both $2261$ and $1275$,
then~$d$ divides their difference $986$ and~$d$ still divides $1275$.
On the other hand, if~$d$ divides both $1275$ and $986$, then it has
to divide their sum $2261$ as well! We have made progress:
$$\gcd(2261,1275) = \gcd(1275,986).$$
This equality also follows by applying
Lemma~\ref{lem:gcdprops}.
Repeating, we have
$$1275 = 1\cdot 986 + 289,$$
so $\gcd(1275,986)=\gcd(986,289)$.
Keep going:
\begin{align*}
986&=3\cdot 289 + 119\\
289&=2\cdot 119 + 51\\
119&=2\cdot 51 + 17.
\end{align*}
Thus $\gcd(2261,1275)=\cdots=\gcd(51,17)$, which is $17$
because $17\mid 51$. Thus
$$\gcd(2261,1275)=17.$$
Aside from some tedious arithmetic, that computation was systematic,
and it was not necessary to factor any integers (which
is something we do not know how to do quickly if the numbers
involved have hundreds of digits).
\begin{algorithm}{Greatest Common Division}
\label{alg:gcd}\index{gcd algorithm}
\index{compute!gcd}
Given integers $a, b$, this algorithm computes $\gcd(a,b)$.
\begin{steps}
\item{} [Assume $a>b> 0$] We have
$\gcd(a,b) = \gcd(|a|,|b|) = \gcd(|b|,|a|)$,
so we may replace $a$ and $b$ by their absolute values and hence
assume $a, b \geq 0$. If $a=b$, output $a$ and
terminate. Swapping if necessary, we assume $a>b$. If $b=0$, we
output $a$.
\item{} [Quotient and Remainder] \label{alg:gcd_usediv} Using Algorithm~\ref{alg:division},
write $a=bq+r$, with $0\leq r<b$ and $q\in\Z$.
\item{} [Finished?] If $r=0$, then $b\mid a$, so we output $b$ and terminate.
\item{} [Shift and Repeat] \label{alg:gcd_shift} Set $a\la b$ and $b \la r$, then go to
Step \ref{alg:gcd_usediv}.
\end{steps}
\end{algorithm}
\begin{proof}
Lemmas~\ref{lem:gcdprops}--\ref{lem:gcdprops2}
imply that $\gcd(a,b) = \gcd(b,r)$ so the gcd does not
change in Step~\ref{alg:gcd_shift}.
Since the remainders form a decreasing sequence of nonnegative
integers, the algorithm terminates.
\end{proof}
\begin{example}
Set $a=15$ and $b=6$.
\begin{eqnarray*}
15 &=& 6\cdot 2 + 3 \qquad\gcd(15,6)=\gcd(6,3)\\
6 &=& 3\cdot 2 + 0 \qquad\gcd(6,3) =\gcd(3,0)=3
\end{eqnarray*}
\end{example}
\noindent{}Note that
we can just as easily do an example that is ten times
as big, an observation that will be important in the
proof of Theorem~\ref{thm:euclid} below.
\begin{example}\label{ex:gcd10}
Set $a=150$ and $b=60$.
\begin{eqnarray*}
150 &=& 60\cdot 2 + 30 \qquad\gcd(150,60)=\gcd(60,30)\\
60 &=& 30\cdot 2 + 0 \qquad\,\,\,\gcd(60,30) =\gcd(30,0)=30
\end{eqnarray*}
\end{example}
\begin{sg}
\sage uses the \code{gcd} command to compute the greatest
common divisor of two integers. For example,
\begin{verbatim}
sage: gcd(97,100)
1
sage: gcd(97 * 10^15, 19^20 * 97^2)
97
\end{verbatim}
\end{sg}
\begin{lemma}\label{lem:gcdmul}
For any integers $a,b,n$, we have
$$\gcd(an,bn) = \gcd(a,b)\cdot |n|.$$
\end{lemma}
\begin{proof}
The idea is to follow Example~\ref{ex:gcd10}; we step through
Euclid's algorithm for $\gcd(an,bn)$ and note that at every step the
equation is the equation from Euclid's algorithm for $\gcd(a,b)$ but
multiplied through by~$n$. For simplicity, assume that both~$a$
and~$b$ are positive. We will prove the lemma by induction on
$a+b$. The statement is true in the base case when $a+b=2$,
since then $a=b=1$. Now assume $a,b$ are arbitrary with $a\geq b$.
Let~$q$ and~$r$ be such that $a = bq + r$ and $0\leq r <b$. Then by
Lemmas~\ref{lem:gcdprops}--\ref{lem:gcdprops2}, we have $\gcd(a,b) =
\gcd(b,r)$. Multiplying $a=bq+r$ by~$n$ we see that $an = bnq +
rn$, so $\gcd(an,bn) = \gcd(bn,rn)$. Then
$$
b+r = b + (a-bq)= a-b(q-1) \leq a < a+b,
$$
so by induction
$\gcd(bn,rn) = \gcd(b,r)\cdot |n|$. Since $\gcd(a,b)=\gcd(b,r)$,
this proves the lemma.
\end{proof}
\begin{lemma}\label{lem:gcd2}
Suppose $a,b,n\in\Z$ are such that $n\mid a$ and $n\mid b$. Then
$n\mid \gcd(a,b)$.
\end{lemma}
\begin{proof}
Since $n\mid a$ and $n\mid b$, there are integers
$c_1$ and $c_2$, such that $a=n c_1$ and $b=n c_2$.
By Lemma~\ref{lem:gcdmul},
$\gcd(a,b) = \gcd(n c_1, nc_2) = n\gcd(c_1, c_2)$,
so $n$ divides $\gcd(a,b)$.
\end{proof}
% At this point it would be natural to formally analyze the complexity
% of Algorithm~\ref{alg:gcd}. We will not do this, because the main
% reason we introduced Algorithm~\ref{alg:gcd} is that it will allow us
% to prove Theorem~\ref{thm:fundamental}, and we have not chosen to
% formally analyze the complexity of the other algorithms in this book.
% For an extensive analysis of the complexity of
% Algorithm~\ref{alg:gcd}, see \cite[\S4.5.3]{knuth2}.
With Algorithm~\ref{alg:gcd}, we can prove that if a prime divides the
product of two numbers, then it has got to divide one of them. This
result is the key to proving that prime factorization
is unique.
\begin{theorem}[Euclid]\label{thm:euclid}%
\index{Euclid's theorem!on divisibility}%
\ithm{Euclid}
Let~$p$ be a prime and $a, b\in \N$.
If $p\mid ab$ then $p\mid a$ or $p\mid b$.
\end{theorem}
You might think this theorem is ``intuitively obvious,'' but that
might be because the fundamental theorem of
arithmetic\index{fundamental theorem of arithmetic}
(Theorem~\ref{thm:fundamental}) is deeply ingrained in your intuition.
Yet Theorem~\ref{thm:euclid} will be needed in our proof of the
fundamental theorem of arithmetic.
\begin{proof}[Proof of Theorem~\ref{thm:euclid}]
If $p\mid a$ we are done. If $p\nmid a$ then $\gcd(p,a)=1$, since
only~$1$ and~$p$ divide~$p$. By Lemma~\ref{lem:gcdmul},
$\gcd(pb,ab) = b$. Since $p\mid pb$ and, by hypothesis, $p\mid ab$,
it follows (using Lemma~\ref{lem:gcdmul}) that
$$p\mid \gcd(pb,ab) = b\gcd(p,a) = b\cdot 1 = b.$$
\end{proof}
\subsection{Numbers Factor as Products of Primes}\label{sec:numfact}
\index{integers!factor}
In this section, we prove that every natural number factors as a
product of primes.
Then we discuss the difficulty of finding such a decomposition
in practice. We will wait until Section~\ref{sec:proof_fundamental}
to prove that factorization is unique.
As a first example, let $n=1275$. The sum of the digits
of $n$ is divisible by $3$, so $n$ is divisible by $3$ (see
Proposition~\ref{prop:div3}), and we have $n=3\cdot 425$.
The number $425$ is divisible by $5$, since its last digit
is $5$, and we have $1275 = 3\cdot 5 \cdot 85$. Again,
dividing $85$ by $5$, we have $1275 = 3\cdot 5^2 \cdot 17$,
which is the prime factorization of $1275$.
%Since $17\mid 1275$,~$n$ is
%definitely composite, $n=17 \cdot 75$. Next, $75$ is $5\cdot
%15=5\cdot 5\cdot 3$, and we find that $1275 = 3\cdot 5\cdot 5\cdot
%17$.
Generalizing this process proves the following proposition.
\begin{proposition}\label{prop:numbers_factor}\iprop{prime factorization}
Every natural number is a product of primes.
\end{proposition}
\begin{proof}
Let~$n$ be a natural number. If $n=1$, then~$n$ is the empty
product of primes.
If $n$ is prime, we are done.
If $n$ is composite, then $n=ab$ with $a,b<n$. By induction,~$a$
and~$b$ are products of primes, so~$n$ is also a product of primes.
\end{proof}
Two questions immediately arise: (1) is this factorization unique, and
(2) how quickly can we find such a factorization? Addressing (1),
what if we had done something differently when breaking apart $1275$
as a product of primes? Could the primes that show up be different?
Let's try: we have $1275 = 5\cdot 255$. Now $255=5\cdot 51$ and
$51=17\cdot 3$, and again the factorization is the same, as asserted
by Theorem~\ref{thm:fundamental}. We will prove the uniqueness
of the prime factorization of
any integer in Section~\ref{sec:proof_fundamental}.
\begin{sg}
The \code{factor} command in \sage factors an integer
as a product of primes with multiplicities. For example,
\begin{verbatim}
sage: factor(1275)
3 * 5^2 * 17
sage: factor(2007)
3^2 * 223
sage: factor(31415926535898)
2 * 3 * 53 * 73 * 2531 * 534697
\end{verbatim}
\end{sg}
Regarding (2), there are algorithms for integer factorization.
It is a major open problem to decide
how fast integer factorization algorithms can be.
We say that an algorithm to factor $n$ is \defn{polynomial time}
if there is a
polynomial $f(x)$ such that for any~$n$ the number of steps needed by
the algorithm to factor~$n$ is less than $f(\log_{10}(n))$. Note
that $\log_{10}(n)$ is an approximation for the number of digits
of the input~$n$ to the algorithm.
\begin{openproblem}\index{open problem!fast integer factorization}
\index{factorization!difficulty of}
Is there an algorithm that can factor any
integer~$n$ in polynomial time?
\end{openproblem}
Peter Shor \cite{shor}\index{Shor} devised a polynomial time algorithm
for factoring integers on quantum computers\index{quantum
computer}\index{factorization!quantum}. We will not discuss his
algorithm further, except to note that in 2001 IBM researchers
built a quantum computer that used Shor's algorithm to factor $15$ (see
\cite{quantum15, ibm:shor15}). Building much larger quantum
computers appears to be extremely difficult.
You can earn money by factoring certain large integers. Many
cryptosystems would be easily broken if factoring certain large
integers was easy. Since nobody has proven that factoring integers
is difficult, one way to increase confidence that factoring is
difficult is to offer cash prizes for factoring certain integers. For
example, until recently there was a \$10,000 bounty on factoring the
following $174$-digit integer (see \cite{rsa:challenge}):
$$
\begin{array}{l}
1881988129206079638386972394616504398071635633794173827007\\
6335642298885971523466548531906060650474304531738801130339\\
6716199692321205734031879550656996221305168759307650257059
\end{array}
$$
This number is known as RSA-576\index{RSA-576} since it has 576
digits when written in binary (see Section~\ref{sec:compute_powers}
for more on binary numbers). It was factored at the German
Federal Agency for Information Technology Security in December
2003 (see \cite{factor576}):
$$
\begin{array}{l}
398075086424064937397125500550386491199064362342526708406\\
\hspace{1ex}385189575946388957261768583317\\
\times\\
472772146107435302536223071973048224632914695302097116459\\
\hspace{1ex}852171130520711256363590397527
\end{array}
$$
The previous RSA challenge was the $155$-digit number
$$
\begin{array}{l}
1094173864157052742180970732204035761200373294544920599091\\
3842131476349984288934784717997257891267332497625752899781\\
833797076537244027146743531593354333897.
\end{array}$$
It was factored on 22 August 1999 by a group of sixteen researchers
in four months on a cluster of 292 computers (see \cite{rsa155}).
They found that RSA-155\index{RSA-155} is the product of the following two
$78$-digit primes:
\begin{align*}
p &= 10263959282974110577205419657399167590071656780803806\\
&\hspace{4ex} 6803341933521790711307779\\
q &= 10660348838016845482092722036001287867920795857598929\\
&\hspace{4ex} 1522270608237193062808643.
\end{align*}
The next RSA challenge is RSA-640:
$$
\begin{array}{l}
31074182404900437213507500358885679300373460228427275457201619\\
48823206440518081504556346829671723286782437916272838033415471\\
07310850191954852900733772482278352574238645401469173660247765\\
2346609,
\end{array}
$$
and its factorization was worth \$20,000 until
November 2005 when it was factored by F. Bahr, M. Boehm, J. Franke,
and T. Kleinjun. This factorization took five months. Here is
one of the prime factors (you can find the other):
$$
\begin{array}{l}
16347336458092538484431338838650908598417836700330923121811108\\
52389333100104508151212118167511579.
\end{array}
$$
(This team also factored a 663-bit RSA challenge integer.)
The smallest currently open challenge is RSA-704, worth \$30,000:
$$
\begin{array}{l}
74037563479561712828046796097429573142593188889231289084936232\\
63897276503402826627689199641962511784399589433050212758537011\\
89680982867331732731089309005525051168770632990723963807867100\\
86096962537934650563796359
\end{array}
$$
\begin{sg}
Using \sage, we see that the above number has 212 decimal digits
and is definitely composite:
\begin{verbatim}
sage: n = 7403756347956171282804679609742957314259318888\
...9231289084936232638972765034028266276891996419625117\
...8439958943305021275853701189680982867331732731089309\
...0055250511687706329907239638078671008609696253793465\
...0563796359
sage: len(n.str(2))
704
sage: len(n.str(10))
212
sage: n.is_prime() # this is instant
False
\end{verbatim}
\end{sg}
These RSA numbers were factored using an algorithm called the number
field sieve (see \cite{lenstras:nfs}), which is the best-known general
purpose factorization algorithm. A description of how the number
field sieve works is beyond the scope of this book. However, the
number field sieve makes extensive use of the elliptic curve
factorization method, which we will describe in Section~\ref{sec:ecm}.
\subsection{The Fundamental Theorem of Arithmetic}%
\label{sec:proof_fundamental}\index{fundamental theorem of arithmetic}
\index{integers!factor uniquely}
We are ready to prove Theorem~\ref{thm:fundamental}
using the following idea.
Suppose we have two factorizations of~$n$. Using
Theorem~\ref{thm:euclid}, we cancel common primes from each factorization,
one prime at a time. At the end,
we discover that the factorizations must
consist of exactly the same primes. The
technical details are given below.
\begin{proof}
If $n=1$, then the only factorization is the empty
product of primes, so suppose $n>1$.
By Proposition~\ref{prop:numbers_factor}, there exist primes
$p_1,\ldots, p_d$ such that
$$
n = p_1 p_2 \cdots p_d.
$$
Suppose that
$$n = q_1 q_2 \cdots q_m$$
is another expression of~$n$ as a product of primes.
Since
$$p_1 \mid n = q_1 (q_2 \cdots q_m),$$
Euclid's theorem implies that $p_1 = q_1$ or
$p_1 \mid q_2\cdots q_m$. By induction, we see that $p_1 = q_i$ for some~$i$.
Now cancel $p_1$ and $q_i$, and repeat the above argument. Eventually,
we find that, up to order, the two factorizations are the same.
\end{proof}
\section{The Sequence of Prime Numbers}
\label{sec:primeseq}\index{primes!sequence of}
This section is concerned with three questions:
\begin{enumerate}
\item Are there infinitely many primes?
\item Given $a,b\in\Z$,
are there infinitely many primes of the form $ax+b$?
\item How are the primes spaced along the number line?
\end{enumerate}
We first show that there are infinitely
many primes, then state Dirichlet's theorem
\index{theorem!of Dirichlet} that if $\gcd(a,b)=1$,
then $ax+b$ is a prime for infinitely many values of~$x$. Finally, we
discuss the Prime Number Theorem\index{prime number theorem}
which asserts that there are
asymptotically $x/\log(x)$ primes less than~$x$,
and we make a connection between this asymptotic formula
and the Riemann Hypothesis\index{Riemann Hypothesis}.
% For some other famous questions
% about the sequence of primes, see Section~\ref{sec:primeassert}.
\subsection{There Are Infinitely Many Primes}\label{sec:inf_primes}
\index{primes!infinitely many}
Each number on the left in the following table is prime.
We will see soon that this pattern does not continue
indefinitely, but something similar works.
\begin{align*}
3 &= 2+1\\
7 &= 2\cdot 3 + 1\\
31 &= 2\cdot 3 \cdot 5 + 1\\
211 &= 2\cdot 3 \cdot 5 \cdot 7 + 1\\
2311 &= 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1
\end{align*}
\begin{theorem}[Euclid]\label{thm:euclid_primes}
There are infinitely many primes.\ithm{infinitely many primes}
\end{theorem}
\begin{proof}
Suppose that $p_1, p_2, \ldots, p_n$ are~$n$ distinct primes.
We construct a prime $p_{n+1}$ not equal to any of $p_1,\ldots, p_n$,
as follows. If
\begin{equation}\label{eqn:infprime}
N=p_1 p_2 p_3 \cdots p_n + 1,
\end{equation}
then by Proposition~\ref{prop:numbers_factor} there is a factorization
$$
N = q_1 q_2 \cdots q_m
$$
with each~$q_i$ prime and $m\geq 1$.
If $q_1 = p_i$ for some~$i$, then $p_i\mid{}N$.
Because of (\ref{eqn:infprime}), we also have
$p_i\mid{}N-1$, so $p_i\mid{} 1=N-(N-1)$, which
is a contradiction.
Thus the prime $p_{n+1} = q_1$ is not in the list $p_1,\ldots, p_n$,
and we have constructed our new prime.
\end{proof}
For example,
$$
2\cdot 3 \cdot 5 \cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509.
$$
Multiplying together the first six primes and adding~$1$ doesn't
produce a prime, but it produces an integer that is merely
divisible by a new prime.
\begin{joke}[Hendrik Lenstra]\index{Lenstra}\index{joke}
There are infinitely many composite numbers. Proof. {\em To obtain
a new composite number, multiply together the first~$n$ composite
numbers and don't add $1$.}
\end{joke}
\subsection{Enumerating Primes}\label{sec:enum_primes}
In this section we describe a sieving process that allows us to
enumerate all primes up to~$n$. The sieve works by first writing down
all numbers up to $n$, noting that~$2$ is prime, and crossing off all
multiples of~$2$. Next, note that the first number not crossed off
is~$3$, which is prime, and cross off all multiples of~$3$, etc.
Repeating this process, we obtain a list of the primes up to~$n$.
Formally, the algorithm is as follows:
\begin{algorithm}{Prime Sieve}\label{alg:sieve}
Given a positive integer $n$, this algorithm computes a list of the
primes up to $n$.
\begin{steps}
\item{}[Initialize] Let $X\assign [3,5,\ldots]$ be the list
of all odd integers between $3$ and $n$. Let $P\assign [2]$ be the list
of primes found so far.
\item{}[Finished?]\label{alg:sieve_2}
Let $p$ be the first element of $X$.
If $p>\sqrt{n}$, append each element of~$X$
to~$P$ and terminate. Otherwise append $p$ to $P$.
\item{}[Cross Off]
Set~$X$ equal to the sublist of elements in~$X$ that
are not divisible by~$p$.
Go to Step~\ref{alg:sieve_2}.
\end{steps}
\end{algorithm}
For example, to list the primes $\leq 40$ using the sieve, we
proceed as follows. First $P=[2]$ and
$$X = [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39].$$
We append $3$ to $P$ and cross off all multiples of $3$ to obtain
the new list
$$X = [5,7,11,13,17,19,23,25,29,31,35,37].$$
Next we append $5$ to $P$, obtaining $P=[2,3,5]$, and cross off
the multiples of $5$, to obtain $X = [7,11,13,17,19,23,29,31,37].$
Because $7^2\geq 40$, we append $X$ to $P$ and find that the
primes less than $40$ are
$$
2,3,5, 7,11,13,17,19,23,29,31,37.
$$
\begin{proof}[Proof of Algorithm~\ref{alg:sieve}]
The part of the algorithm that is not clear is that
when the first element $a$ of $X$ satisfies $a\geq \sqrt{n}$,
then each element of $X$ is prime.
To see this, suppose $m$ is in $X$, so
$\sqrt{n} \leq m\leq n$ and that~$m$ is divisible by
no prime that is $\leq \sqrt{n}$. Write $m=\prod p_i^{e_i}$ with
the $p_i$ distinct primes ordered so that $p_1<p_2<\ldots$. If $p_i>\sqrt{n}$
for each~$i$ and there is more than one~$p_i$, then $m>n$,
a contradiction. Thus some~$p_i$ is less than $\sqrt{n}$,
which also contradicts our assumptions on~$m$.
\end{proof}
\subsection{The Largest Known Prime}\label{sec:largest}\index{primes!largest known}
\index{largest known!prime}
Though Theorem~\ref{thm:euclid_primes} implies that there are infinitely
many primes, it still makes sense to ask the question
``What is the largest {\em known} prime?''
A \defn{Mersenne prime} is a prime of the form $2^q-1$.
According to \cite{caldwell:largestprime} the largest known prime
as of March 2007 is the 44th known Mersenne prime\index{primes!Mersenne}
$$
p = 2^{32582657}-1,
$$
which has 9,808,358 decimal
digits\footnote{The 49th known Mersenne prime may
have been found on January 7, 2016.}.
This would take over 2000 pages to
print, assuming a page contains 60 lines with 80 characters per line.
The Electronic Frontier Foundation has offered a \$100,000 prize to
the first person who finds a 10,000,000 digit prime.
Euclid's theorem implies that there definitely are infinitely
many primes bigger than~$p$.
Deciding whether or not a number is prime is
interesting, as a theoretical problem,
and as a problem with
applications to cryptography\index{cryptography}, as we will see in
Section~\ref{sec:prob_prime_test} and Chapter~\ref{ch:crypto}.
\begin{sg}
We can compute the decimal expansion of $p$ in \sage, although
watch out as this is a serious computation that may take
around a minute on your computer. Also, do not print
out $p$ or $s$ below, because both would take a very
long time to scroll by.
\begin{verbatim}
sage: p = 2^32582657 - 1
sage: p.ndigits()
9808358
\end{verbatim}%link
\noindent{}Next we convert $p$ to a decimal string and look at some of the digits.
%link
\begin{verbatim}
sage: s = p.str(10) # this takes a long time
sage: len(s) # s is a very long string (long time)
9808358
sage: s[:20] # the first 20 digits of p (long time)
'12457502601536945540'
sage: s[-20:] # the last 20 digits (long time)
'11752880154053967871'
\end{verbatim}
\end{sg}
\subsection{Primes of the Form $ax+b$}
\index{primes!of form $ax+b$}
Next we turn to primes of the form $ax+b$, where~$a$ and~$b$ are
fixed integers with $a>1$ and~$x$ varies over the natural numbers $\N$.
We assume that $\gcd(a,b)=1$, because otherwise there is no
hope that $ax+b$ is prime infinitely often.
For example, $2x+2=2(x+1)$ is only prime if $x=0$, and is
not prime for any $x\in\N$.
\begin{proposition}\index{primes!of form $4x-1$}\label{prop:4x-1}
\iprop{infinitely many primes}
There are infinitely many primes of the form $4x-1$.
\end{proposition}
Why might this be true? We list numbers of the form $4x-1$ and underline
those that are prime.
$$\ul{3},\, \ul{7},\, \ul{11},\, 15,\, \ul{19},\, \ul{23},\, 27,\, \ul{31},\, 35,\, 39,\,
\ul{43},\, \ul{47},\, \ldots$$
Not only is it plausible that underlined numbers will continue to appear
indefinitely, it is something we can easily prove.
\begin{proof}
Suppose $p_1, p_2,\ldots, p_n$ are distinct primes of the form $4x-1$. Consider
the number
$$
N = 4p_1 p_2 \cdots p_n - 1.
$$
Then $p_i \nmid N$ for any~$i$. Moreover, not every prime $p\mid N$
is of the form $4x+1$; if they all were, then $N$ would be of the form
$4x+1$. Since $N$ is odd, each prime divisor $p_i$ is odd so
there is a $p\mid N$ that is of the form $4x-1$. Since
$p\not= p_i$ for any~$i$, we have found a new prime of the form
$4x-1$. We can repeat this process indefinitely, so the set of primes
of the form $4x-1$ cannot be finite.
\end{proof}
Note that this proof does not work if $4x-1$ is replaced by $4x+1$,
since a product of primes of the form $4x-1$ can be of the form
$4x+1$.
\begin{example}\label{ex:inf_prime_form}
Set $p_1=3$, $p_2=7$. Then
$$
N = 4\cdot 3 \cdot 7 - 1 = \ul{83}
$$
is a prime of the form $4x-1$. Next
$$
N = 4\cdot 3 \cdot 7\cdot 83 - 1 = \ul{6971},
$$
which is again a prime of the form $4x-1$.
Again,
$$