100. The Greek mathematician E
UCLID
(ca. 300
B
.
C
.
E
.)
was the first to prove that the list of primes goes on
forever. Today we call his particular argument establish-
ing this E
UCLID
’
S PROOF OF THE INFINITUDE OF PRIMES
.
Every whole number can be written as a product of
prime numbers. (If the number is already prime, it is con-
sidered a product with just one term.) For example, the
number 100 can be factored as 2 ×2 ×5 ×5. For this
reason, primes are considered the multiplicative building
blocks of the natural numbers, and have therefore been
the object of much intensive study throughout the cen-
turies. Surprisingly, many basic questions about them
remain unsolved. For example, no one knows a simple
formula that will generate the prime numbers, or a sim-
ple, and computationally feasible, procedure for factoring
large numbers into primes. It is not known whether
infinitely many
TWIN PRIMES
exist, or whether, as C
HRIS
-
TIAN
G
OLDBACH
(1690–1764) conjectured, every even
number greater than 2 is indeed a sum of two primes.
(This is known as G
OLDBACH
’
S CONJECTURE
.) Also, no
one knows if there are infinitely many prime numbers of
the form n2+ 1, that is, 1 more than a square number, or
whether between any two square numbers there must be
a prime. (It is known, however, that for any number n
greater than 1, there is a prime between nand 2n.)
In 1791 C
ARL
F
RIEDRICH
G
AUSS
(1777–1855) con-
jectured that the nth prime number has value approxi-
mately n· ln(n) where ln(n) is the natural
LOGARITHM
of n. This claim was later proved to be correct and is
today called the
PRIME
-
NUMBER THEOREM
.
Despite the infinitude of primes, these numbers, in
some sense, are very scarce. It is easy to produce an arbi-
trarily long string of consecutive integers, none of which
are prime. For example, making use of the
FACTORIAL
function, the numbers 1001! + 2, 1001! + 3, up to 1001!
+ 1001 form a string of 1,000 consecutive composite
numbers. (These numbers are, respectively, divisible by
2,3,…,1001.) The
SIEVE OF
E
RATOSTHENES
can be used
to “sift out” the prime numbers up to any given integer.
Prime numbers, especially large prime numbers,
play a key role in
CRYPTOGRAPHY
. The discovery of
new, large prime numbers is of interest to financial
institutions and security services needing to develop
effective encryption codes. Large prime numbers are
discovered with the aid of a computer, and are typically
M
ERSENNE PRIMES
. The largest prime number known
as of the year 2003 is 220,996,011 – 1. It is over 6 million
digits long.
French mathematician and lawyer P
IERRE DE
F
ER
-
MAT
(1601–65) proved that if pis a prime number, then
2p–1– 1 will be divisible by p. If not, it means the num-
ber pwas not prime to begin with. This is often used as
a test to determine whether a number pis a good candi-
date for being prime. Unfortunately, some numbers can
still pass the test without being prime. For example, 2340
– 1 turns out to be divisible by 341, even though the
number 341 is not prime (341 = 11 ×31). Composite
numbers that pass Fermat’s test are called pseudoprimes.
The first three pseudoprimes are 341, 561, and 645.
See also
COMPOSITE NUMBER
;
FACTOR
.
prime-number theorem Mathematicians define π(n)
to be the number of
PRIME
s less than or equal to n. For
example, there are four prime numbers less than 10,
and so π(10) = 4. The quantity thus measures the
proportion of numbers up to nthat are prime. Study of
this function is important to understanding the distri-
bution of prime numbers among the natural numbers.
At the age of 14, mathematician C
ARL
F
RIEDRICH
G
AUSS
(1777–1855) developed a passion for tabulating
data about prime numbers. He observed, among other
things, that the inverted function r(n) = seems to
increase in value by constant amount 2.31 with each 10-
fold increase of n, at least for large values of n. That is,
r(10n) ≈r(n) + 2.31
For example, r(100,000,000) equals ≈
1
––––––
0.05761455
n
––
π(n)
π(n)
––
n
410 prime-number theorem
nπ(n)
10 4 0.4
100 25 0.25
1,000 168 0.168
10,000 1,229 0.1229
100,000 9,592 0.09592
1,000,000 78,498 0.078498
10,000,000 664,579 0.0664579
100,000,000 5,761,455 0.05761455
1,000,000,000 45,505,251 0.045505251
π(n)
––
n