What is a prime number?
A prime number is
a positive integer that has exactly two positive integer
factors, 1 and itself. For example, if we list the
factors of 28, we have 1, 2, 4, 7, 14, and 28. That's
six factors. If we list the factors of 29, we only have
1 and 29. That's 2. So we say that 29 is a prime number,
but 28 isn't.
Another way of
saying this is that a prime number is a whole number
that is not the product of two smaller numbers.
Note that the
definition of a prime number doesn't allow 1 to be a
prime number: 1 only has one factor, namely 1. Prime
numbers have exactly two factors, not "at most
two" or anything like that. When a number has more than
two factors it is called a composite number.
Here are the first
few prime numbers:
2, 3, 5, 7, 11,
13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199,
The Largest Known Primes
on the Web
What are Mersenne
primes and why do we search for them?
A Mersenne prime is a prime
of the form 2P-1. The first Mersenne primes are 3, 7,
31, 127, etc. There are only 41 known Mersenne primes.
GIMPS, the Great Internet
Mersenne Prime Search, was formed in January 1996 to discover
new world-record-size Mersenne primes. GIMPS harnesses the power
of thousands of small computers like yours to search for these
"needles in a haystack".
Most GIMPS members join the
search for the thrill of possibly discovering a record-setting,
rare, and historic new Mersenne prime. Of course, there are many
more information about Mersenne primes , History ,Theorems and
click here .
Why do people find these primes?
"Why?" we are often asked,
"why would anyone want to find a prime that big?"" I often now
answer with "did you ever collect anything?"" or "did you ever
try to win a competition?"" Much of the answer for why we
collect large primes is the same as why we might collect other
rare items. Below I will present a more complete answer divided
into several parts.
For the by-products of the
People collect rare and beautiful items
For the glory!
To test the hardware
To learn more about their distribution
This does not exhaust the
list of reasons, for example some might be motivated by primary
research or a need for publication. Many others just hate to see
a good machine wasting cycles (sitting idle or running an inane
Perhaps these arguments
will not convince you. If not, just recall that the eye may not
see what the ear hears, but that does not reduce the value of
sound. There are always melodies beyond our grasp.
Euclid may have been the
first to define primality in his Elements approximately 300 BC.
His goal was to characterize the even perfect numbers (numbers
like 6 and 28 who are equal to the sum of their aliquot
divisors: 6 = 1+2+3, 28=1+2+4+7+14). He realized that the even
perfect numbers (no odd perfect numbers are known) are all
closely related to the primes of the form 2p-1
for some prime p (now called Mersennes). So the quest for
these jewels began near 300 BC.
Large primes (especially of
this form) were then studied (in chronological order) by Cataldi,
Descartes, Fermat, Mersenne, Frenicle, Leibniz, Euler, Landry,
Lucas, Catalan, Sylvester, Cunningham, Pepin, Putnam and Lehmer
(to name a few). How can we resist joining such an illustrious
Much of elementary number
theory was developed while deciding how to handle large numbers,
how to characterize their factors and discover those which are
prime. In short, the tradition of seeking large primes
(especially the Mersennes) has been long and fruitful It is a
tradition well worth continuing.
2. For the
by-products of the quest
Being the first to put a
man on the moon had great political value for the United States
of America, but what was perhaps of the most lasting value to
the society was the by-products of the race. By-products such
as the new technologies and materials that were developed for
the race that are now common everyday items, and the
improvements to education's infrastructure that led many man and
women into productive lives as scientists and engineers.
The same is true for the
quest for record primes. In the tradition section above I
listed some of the giants who were in the search (such as
Euclid, Euler and Fermat). They left in their wake some of the
greatest theorems of elementary number theory (such as Fermat''s
little theorem and quadratic reciprocity).
More recently, the search
has demanded new and faster ways of multiplying large integers.
In 1968 Strassen discovered how to multiply quickly using
Fast Fourier Transforms.
He and Schönhage refined and published the method in 1971. GIMPS
now uses an improved version of their algorithm developed by the
long time Mersenne searcher Richard Crandall .
The Mersenne search is also
used by school teachers to involve their students in
mathematical research, and perhaps to excite them into careers
in science or engineering. And these are just a few of the
by-products of the search.
collect rare and beautiful items
Mersenne primes, which are
usually the largest known primes, are both rare and beautiful.
Since Euclid initiated the search for and study of Mersennes
approximately 300 BC, very few have been found. Just 37 in all
of human history--that is rare!
But they are also
beautiful. Mathematics, like all fields of study, has a
definite notion of beauty. What qualities are perceived as
beautiful in mathematics? We look for proofs that are short,
concise, clear, and if possible that combine previous disparate
concepts or teach you something new. Mersennes have one of the
simplest possible forms for primes, 2n-1. The
proof of their primality has an elegant simplicity. Mersennes
are beautiful and have some surprising applications.
4. For the
Why do athletes try to run
faster than anyone else, jump higher, throw a javelin further?
Is it because they use the skills of javelin throwing in their
jobs? Not likely. More probably it is the desire to compete
(and to win!)
This desire to compete is
not always directed against other humans. Rock climbers may see
a cliff as a challenge. Mountain climbers can not resist certain
Look at the incredible size
of these giant primes! Those who found them are like the
athletes in that they outran their competition. They are like
the mountain climbers in that they have scaled to new heights.
Their greatest contribution to mankind is not merely pragmatic,
it is to the curiosity and spirit of man. If we lose the desire
to do better, will we still be complete?
5. To test
Since the dawn of
electronic computing, programs for finding primes have been used
as a test of the hardware. For example, software routines from
the GIMPS project were used by Intel to test Pentium II and
Pentium Pro chips before they were shipped. So a great many of
the readers of this page have directly benefited from the
search for Mersennes.
Slowinski, who has help
find more Mersennes than any other, works for Cray Research and
they use his program as a hardware test. The infamous Pentium
bug was found in a related effort as
was calculating the twin prime constant.
Why are prime programs used
this way? They are intensely CPU and bus bound. They are
relatively short, give an easily checked answer (when run on a
known prime they should output true after their billions of
calculations). They can easily be run in the background while
other "more important" tasks run, and they are usually easy to
stop and restart.
learn more about their distribution
Though mathematics is not
an experimental science, we often look for examples to test
conjectures (which we hope to then prove). As the number of
examples increase, so does (in a sense) our understanding of the