100. The Greek mathematician EUCLID (ca. 300 B.C.E.)
was the first to prove that the list of primes goes on
forever. Today we call his particular argument establishing this EUCLID’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 considered 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 centuries. Surprisingly, many basic questions about them
remain unsolved. For example, no one knows a simple
formula that will generate the prime numbers, or a simple, and computationally feasible, procedure for factoring
large numbers into primes. It is not known whether
infinitely many TWIN PRIMES exist, or whether, as CHRISTIAN GOLDBACH (1690–1764) conjectured, every even
number greater than 2 is indeed a sum of two primes.
(This is known as GOLDBACH’S CONJECTURE.) Also, no
one knows if there are infinitely many prime numbers of
the form n
2 + 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 n and 2n.)
In 1791 CARL FRIEDRICH GAUSS (1777–1855) conjectured that the nth prime number has value approximately 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 arbitrarily 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 ERATOSTHENES 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
MERSENNE PRIMES. The largest prime number known
as of the year 2003 is 2
20,996,011 – 1. It is over 6 million
digits long.
French mathematician and lawyer PIERRE DE FERMAT (1601–65) proved that if p is a prime number, then
2
p–1 – 1 will be divisible by p. If not, it means the number p was not prime to begin with. This is often used as
a test to determine whether a number p is a good candidate for being prime. Unfortunately, some numbers can
still pass the test without being prime. For example, 2
340
– 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 PRIMEs 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 n that are prime. Study of
this function is important to understanding the distribution of prime numbers among the natural numbers.
At the age of 14, mathematician CARL FRIEDRICH
GAUSS (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 10fold 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
was the first to prove that the list of primes goes on
forever. Today we call his particular argument establishing this EUCLID’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 considered 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 centuries. Surprisingly, many basic questions about them
remain unsolved. For example, no one knows a simple
formula that will generate the prime numbers, or a simple, and computationally feasible, procedure for factoring
large numbers into primes. It is not known whether
infinitely many TWIN PRIMES exist, or whether, as CHRISTIAN GOLDBACH (1690–1764) conjectured, every even
number greater than 2 is indeed a sum of two primes.
(This is known as GOLDBACH’S CONJECTURE.) Also, no
one knows if there are infinitely many prime numbers of
the form n
2 + 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 n and 2n.)
In 1791 CARL FRIEDRICH GAUSS (1777–1855) conjectured that the nth prime number has value approximately 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 arbitrarily 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 ERATOSTHENES 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
MERSENNE PRIMES. The largest prime number known
as of the year 2003 is 2
20,996,011 – 1. It is over 6 million
digits long.
French mathematician and lawyer PIERRE DE FERMAT (1601–65) proved that if p is a prime number, then
2
p–1 – 1 will be divisible by p. If not, it means the number p was not prime to begin with. This is often used as
a test to determine whether a number p is a good candidate for being prime. Unfortunately, some numbers can
still pass the test without being prime. For example, 2
340
– 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 PRIMEs 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 n that are prime. Study of
this function is important to understanding the distribution of prime numbers among the natural numbers.
At the age of 14, mathematician CARL FRIEDRICH
GAUSS (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 10fold 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