chap4.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

infinitely many primes; but for any particular~$n$ all but a few
exponents are zero, so the corresponding factors are~$1$. Therefore it's really
a finite product, just as many ``infinite'' sums are really finite
because their terms are mostly zero.

Formula \thiseq\ represents $n$ uniquely, so we can think of
the sequence $\langle n_2,n_3,n_5,\ldots\,\rangle$ as a {\it"number system"\/}
for positive integers. For example, the "prime-exponent representation"
of $12$ is $\langle 2,1,0,0,\ldots\,\rangle$ and the prime-exponent representation
of $18$ is $\langle 1,2,0,0,\ldots\,\rangle$. To multiply
two numbers, we simply add their representations. In other words,
\setmathsize{k=\gcd(m,n)\kern-10pt}%
\begindisplay
\mathsize{k=mn}\qquad\iff\qquad k_p=m_p+n_p\quad\hbox{for all $p$}.
\eqno\eqref|prod-exp|
\enddisplay
This implies that
\begindisplay
\mathsize{m\divides n}\qquad\iff\qquad m_p\le n_p\quad\hbox{for all $p$},
\eqno\eqref|div-exp|
\enddisplay
and it follows immediately that
\begindisplay
\mathsize{k=\gcd(m,n)\kern-10pt}
 \qquad\iff\qquad k_p=\min(m_p,n_p)\quad\hbox{for all $p$};
\eqno\eqref|gcd-exp|\cr
\mathsize{k=\lcm(m,n)\kern-10pt}
 \qquad\iff\qquad k_p=\max(m_p,n_p)\quad\hbox{for all $p$}.
\eqno\eqref|lcm-exp|
\enddisplay
For example, since $12=2^2\cdt3^1$ and $18=2^1\cdt3^2$, we can get their
"!greatest common divisor" "!least common multiple"
gcd and lcm by taking the min and max of common exponents:
\begindisplay
\gcd(12,18)&=2^{\min(2,1)}\cdot3^{\min(1,2)}=2^1\cdt3^1=6\,;\cr
\noalign{\nobreak}
\lcm(12,18)&=2^{\max(2,1)}\cdot3^{\max(1,2)}=2^2\cdt3^2=36\,.\cr
\enddisplay

If the prime $p$ divides a product $mn$ then it divides either
$m$ or~$n$, perhaps both, because of the unique
factorization theorem. But composite numbers do not have this property.
For example, the nonprime~$4$ divides $60=6\cdt10$, but it divides neither
$6$ nor~$10$. The reason is simple: In the factorization $60=6\cdt10=
(2\cdt3)(2\cdt5)$, the two prime factors of $4=2\cdt2$ have been split
into two parts, hence $4$ divides neither part. But a prime is
unsplittable, so it must divide one of the original factors.

\beginsection 4.3 Prime examples

How many primes are there? A lot. In fact, infinitely many. "Euclid"
proved this long ago in his Theorem 9\thinspace:\thinspace20, as
follows. Suppose there were only finitely many primes, say $k$ of them\dash---%
$2$,~$3$, $5$, \dots,~$P_k$. Then, said Euclid, we should consider the number
\def\br#1#2{{\buildrel\hbox{\gmathtext#1}\over{\smash#2}}}%
\g\mathsurround=0pt \textfont1=\gtfont \advance\baselineskip1pt
\mathchardef\varsigma=294 % "0126
\noindent\llap{``}$@O\br`\iota$ $\pi\rho\tilde\omega\tau o\iota$
$\br'\alpha\rho\iota\theta\mu o\grave\iota$
$\pi\lambda\epsilon\acute\iota o\upsilon\varsigma$
$\epsilon\br'\iota\sigma\grave\iota$
$\pi\alpha\nu\tau\grave o\varsigma$
$\tau o\tilde\upsilon$
$\pi\rho o\tau\epsilon\theta\acute\epsilon\nu\tau o\varsigma$
$\pi\lambda\acute\eta\theta o\upsilon\varsigma$
$\pi\rho\acute\omega\tau\omega\nu$
$\br'\alpha\rho\iota\theta\mskip-1mu\mu\tilde\omega\nu$.''\par
\hfill\dash---Euclid [|euclid-elts|]
\smallskip \advance\baselineskip-1pt
[Translation:\par
\noindent\llap{``}There are more primes than in any given set of~primes.'']\g
\begindisplay
M=2\cdot3\cdot5\cdot\ldots\cdot P_k\;+\;1\,.
\enddisplay
None of the $k$ primes can divide $M$, because each divides $M-1$. Thus there
must be some other prime that divides~$M$; perhaps $M$~itself is prime. This
contradicts our assumption that $2$,~$3$, \dots,~$P_k$ are the only
primes, so there must indeed be infinitely many.

Euclid's proof suggests that we define {\it "Euclid numbers"\/} by the
recurrence
\begindisplay
e_n&=e_1e_2\ldots e_{n-1}\,+\,1\,,\qquad\hbox{when $n\ge1$}.
\eqno\eqref|euclid-rec|
\enddisplay
The sequence starts out
\begindisplay
e_1&=1+1=2\,;\cr
e_2&=2+1=3\,;\cr
e_3&=2\cdt3+1=7\,;\cr
e_4&=2\cdt3\cdt7+1=43\,;\cr
\enddisplay
these are all prime. But the next case, $e_5$, is $1807=13\cdt139$.
It turns out that $e_6=3263443$ is prime, while
\begindisplay
e_7&=547\cdt607\cdt1033\cdt31051\,;\cr
e_8&=29881\cdt67003\cdt9119521\cdt6212157481\,.\cr
\enddisplay
It is known that $e_9$, \dots, $e_{17}$ are composite, and the remaining
$e_n$ are probably composite as well. However, the Euclid numbers are
all {\it "relatively prime"\/} to each other; that is,
\begindisplay
\gcd(e_m,e_n)=1\,,\qquad\hbox{when $m\ne n$.}
\enddisplay
Euclid's algorithm (what else?)\ tells us this in three short steps,
because $e_n\bmod e_m=1$ when $n>m$:
\begindisplay
\gcd(e_m,e_n)=\gcd(1,e_m)=\gcd(0,1)=1\,.
\enddisplay
Therefore,
if we let $q_j$ be the smallest factor of~$e_j$ for all $j\ge1$,
the primes $q_1$, $q_2$, $q_3$, \dots\ are all different. This
is a sequence of infinitely many primes.

Let's pause to consider the Euclid numbers from the standpoint of
Chapter~1. Can we express $e_n$ in "closed form"?
Recurrence \thiseq\ can be simplified by removing the three dots:
If $n>1$ we have
\begindisplay
e_n=e_1\ldots e_{n-2}e_{n-1}+1=(e_{n-1}-1)e_{n-1}+1=e_{n-1}^2-e_{n-1}+1\,.
\enddisplay
Thus $e_n$ has about twice as many decimal digits as $e_{n-1}$.
Exercise~|euclid-sol-proof| proves that there's a constant
$E\approx1.264$ such that
\begindisplay
\textstyle e_n=\bigl\lfloor E^{2^n}+\half\bigr\rfloor\,.
\eqno\eqref|euclid-sol|
\enddisplay
And exercise |mills-proof| provides a similar formula that gives nothing but primes:
\begindisplay
p_n=\bigl\lfloor P^{3^n}\bigr\rfloor\,,
\eqno\eqref|mills-primes|
\enddisplay
for some constant $P$. But equations like
\eq(|euclid-sol|) and \thiseq\ cannot really be considered to be in
closed form, because the constants $E$ and $P$ are computed
from the numbers $e_n$ and~$p_n$ in a sort of sneaky way. No
independent relation is known (or likely) that would connect them with
other constants of mathematical interest.

Indeed,
nobody knows {\it any\/} useful formula that gives arbitrarily large
primes but only primes. Computer scientists at Chevron
Geosciences did, however,
strike mathematical oil in 1984. Using a program developed
by David "Slowinski", they discovered the
"!prime, largest known"
largest prime known at that time,
\begindisplay
2^{216091}-1\,,
\enddisplay
while testing a new "Cray X-MP" supercomputer. It's easy to compute
this number in a few milliseconds on a "personal computer", because
modern computers work in binary notation and this number is simply
$(11\ldots1)_2$. All 216,091 of its bits are `$1$'. But it's much
harder to prove that this number is prime. In fact, just about any
computation with it takes a lot of time, because it's so large. For
example, even a sophisticated algorithm requires several minutes
just to convert $2^{216091}-1$ to
radix~$10$ on a~PC. When printed out, its 65,050 decimal digits require
\g Or probably more, by the time you read this.\g
75~cents U.S. postage to mail first class.

Incidentally, $2^{216091}-1$ is the number of moves necessary to solve
the "Tower of Hanoi" problem when there are 216,091 disks.
Numbers of the form
\begindisplay
2^p-1
\enddisplay
(where $p$ is prime, as always in this chapter) are called {\it
"Mersenne numbers"}, after Father Marin "Mersenne" who investigated some of
their properties in the seventeenth century~[|mersenne|].                . 
%The second- and fourth-largest known primes, discovered by David
%"Slowinski" using a Cray, are also Mersenne numbers, with $p=132049$
%and $p=86243$.
The Mersenne primes known to date occur for $p=2$, $3$, $5$, $7$, $13$,
$17$, $19$, $31$, $61$, $89$, $107$, $127$, $521$, $607$, $1279$,
$2203$, $2281$, $3217$, $4253$, $4423$, $9689$, $9941$, $11213$, $19937$,
$21701$, $23209$, $44497$, $86243$, $110503$, $132049$, $216091$,
and $756839$.

The number $2^n-1$ can't possibly be prime if $n$ is composite,
because $2^{km}-1$ has $2^m-1$ as a factor:
\begindisplay
2^{km}-1=(2^m-1)(2^{m(k-1)}+2^{m(k-2)}+\cdots+1)\,.
\enddisplay
But $2^p-1$ isn't always prime when $p$ is prime; $2^{11}-1=2047
=23\cdt89$ is the smallest such nonprime. (Mersenne knew this.)

"Factoring" and "primality testing" of large numbers are hot topics
nowadays. A summary of what was known up to~1981 appears in
Section 4.5.4 of [|knuth2|], and many new results continue
to be discovered. Pages 391--394 of that book explain a
special way to test Mersenne numbers for primality.

 For most of
the last two hundred years, the largest known prime has been a
Mersenne prime, although only 31 Mersenne primes are known. Many people
are trying to find larger ones, but it's getting tough. So those
really interested in fame (if not fortune) and a spot in {\sl
The Guinness Book of World Records\/} might instead try numbers
of the form $2^nk+1$, for small values of~$k$ like $3$ or~$5$.
These numbers can be tested for primality almost as quickly
as Mersenne numbers can; exercise 4.5.4--27 of~[|knuth2|] gives the details.

We haven't fully answered our original question about how many
primes there are. There are infinitely many, but some infinite
sets are ``denser'' than others. For instance,
among the positive integers there are infinitely many
even numbers and infinitely many perfect squares,
yet in several important senses
there are more even numbers than perfect squares.
\g Weird. I thought there were the same number of even integers
as perfect squares, since there's a one-to-one correspondence
between them.\g
One such sense looks at the size of the $n$th value.
The $n$th even integer is $2n$ and
the $n$th perfect square is $n^2$;
since $2n$ is much less than $n^2$ for large~$n$,
the $n$th even integer occurs much sooner than the $n$th perfect square,
so we can say there are many more even integers than perfect squares.
A similar sense looks at the number of values not exceeding~$x$.
There are $\lfloor x/2 \rfloor$ such even integers and
$\lfloor \sqrt{x} @\rfloor$ perfect squares;
since $x/2$ is much larger than~$\sqrt{x}$ for large~$x$,
again we can say there are many more even integers.

What can we say about the primes in these two senses?
It turns out that
the $n$th prime, $P_n$, is about $n$ times the natural log of~$n$:
\begindisplay
P_n
	\sim n \ln n\,.
\enddisplay
(The symbol `$\sim$' can be read ``is "asymptotic" to'';
it means that the limit of the ratio $P_n/n \ln n$ is~$1$
as $n$~goes to infinity.)
Similarly, for the number of primes~$\pi(x)$ not exceeding~$x$
we have what's known as the prime number theorem:
\begindisplay
\pi(x)
	\sim {x\over \ln x} \,.
\enddisplay
Proving these two facts is beyond the scope of this book,
although we can show easily that each of them implies the other.
In Chapter~9 we will discuss the rates at which functions
approach infinity, and we'll see that the function $n \ln n$,
our approximation to~$P_n$, lies between $2n$ and $n^2$ asymptotically.
Hence there are fewer primes than even integers,
but there are more primes than perfect squares.

These formulas, which hold only in the limit as $n$ or $x\to\infty$,
can be replaced by more exact estimates. For example, "Rosser" and
"Schoenfeld"~[|rosser-schoenfeld|] have established the handy bounds
\begindisplay
&\textstyle
\ln x-{3\over2}<{x\over\pi(x)}<\ln x-{1\over2}\,,&\hbox{for $x\ge67$};
\eqno\eqref|prime-theorem|\cr
&\textstyle n\bigl(\ln n+\ln\ln n-{3\over2}\bigr)\!<\!P_n\!<\!
 n\bigl(\ln n+\ln\ln n-\half\bigr), \ \ &\hbox{for $n\ge20$}.
\eqno\eqref|dual-prime-theorem|\cr
\enddisplay

If we look at a ``random'' integer~$n$, the chances of its being prime
are about one~in~$\ln n$. For example, if we look at numbers near~$10^{16}$,
we'll have to examine about $16\ln 10\approx36.8$ of them before
finding a prime. (It turns out that there are exactly 10~primes between
$10^{16}-370$ and $10^{16}-1$.) Yet the distribution of primes has
many irregularities. For example, all the numbers between
$P_1P_2\ldots P_n+2$ and $P_1P_2\ldots P_n+P_{n+1}-1$ inclusive are composite.
Many examples of ``twin primes'' $p$~and~$p+2$ are known
($5$~and~$7$,
$11$~and~$13$,
$17$~and~$19$,
$29$~and~$31$, \dots,
$9999999999999641$ and $9999999999999643$, \dots\thinspace), yet nobody
knows whether or not there are infinitely many pairs of twin primes.
(See "Hardy" and "Wright"~[|hardy-wright|, \S1.4 and \S2.8].)

One simple way to calculate all $\pi(x)$~primes $\le x$
is to form the so-called "sieve" of "Eratosthenes":
First write down all integers from $2$~through~$x$.
Next circle~$2$, marking it prime, and cross out all other multiples of~$2$.
Then repeatedly circle the smallest uncircled, uncrossed number and
cross out its other multiples.
When everything has been circled or crossed out,
the circled numbers are the primes.
For example when $x=10$ we write down $2$~through~$10$,
circle~$2$, then cross out its multiples $4$,~$6$, $8$, and~$10$.
Next $3$~is the smallest uncircled, uncrossed number,
so we circle it and cross out $6$ and~$9$.
Now $5$~is smallest, so we circle it and cross out~$10$.
Finally we circle~$7$.
The circled numbers are $2$,~$3$, $5$, and~$7$;
so these are the $\pi(10) = 4$ primes not exceeding~$10$.

\beginsection 4.4 Factorial Factors

Now let's take a look at the "factorization" of some interesting highly
\g\vskip-54pt
 \noindent\llap{``}Je me sers de la notation tr\`es simple $n!$ pour d\'esigner
le produit de nombres d\'ecroissans depuis $n$ jusqu'\`a l'unit\'e,
savoir $n(n-1)\break(n-2)\mskip-1mu\ldots.\,\,3.\,2.\,1\mskip-2mu.$\break