spaf@gatech.UUCP (10/23/83)
(My apologies if I repeat some points presented earlier, but I thought
some historical perspective might be nice.)
The French monk, Father Marin Mersenne (1588-1648), originally asserted
in his work "Cogitata Physica-Mathematica" (1644) that certain numbers
were prime. These numbers were of the form (2^p-1) with p = 2, 3, 5,
7, 13, 17, 19, 31, 67, 127, and 257. He also stated that for all the
other values of p < 257, these numbers were composite. Numbers of this
form came to be known as "Mersenne's numbers" and his conjecture was
basically unprovable due to the state of computational abilites (at the
time). In 1772 Euler showed that for p=31 the Mersenne number was,
indeed, prime. It wasn't until 1947 that all values of p < 257 were
tested; this resulted in showing that Mersenne had made five errors:
M67 and M257 are not prime, and M61, M89, and M107 are all prime.
It is fairly well known that if a number (a^k-1) is prime, then a must
be equal to 2 and k must also be prime (for a>0 and k>1). This is
because (a^k-1) can be factored using simple algebra to contain the
factor (a-1) -- thus, to be prime, a must be 2. Also, if k is
composite, equal to r*s, then (a^k-1) is equal to ((a^r)^s-1) and is
factorable by (a^r-1). It is obvious therefore that k must be prime.
Certain properties of Mersenne numbers are known. For instance, if p
and q=2p+1 are both odd primes with p equivalent to 3 mod 4, then q
divides Mp (2^p-1). It is also known that any odd divsor of Mp, if p
is an odd prime, is of the form 2kp+1 and any odd prime divisor q is
equivalent to plus or minus 1, mod 8. I have listed, below, the 29
known Mersenne primes and approximate date of discovery. My source
(Burton's "Elementary Number Theory") only contained the first 24 since
no others were proven correct at that time. I believe that the 29th is
only conjectured but not yet proven (anyone else know?).
Number Date
------ ----
2 unknown (antiquity)
3 unknown (antiquity)
5 unknown (antiquity)
7 unknown (antiquity)
13 1456
17 1588
19 1588
31 1722
61 1883
89 1911
107 1914
127 1876
521 1952
607 1952
1279 1952
2203 1952
2281 1952
3217 1957
4253 1961
4423 1961
9689 1963
9941 1963
11213 1963
19937 1971
21701
23209
44497
86243
132049 1983 (unverified?)
As an additional note of historical interest, the factors of M67 were
not known until 1903, although it was shown by Edouard Lucas in 1876 to
be composite. In October 1903, at an AMS meeting, Frederick Nelson
Cole proceeded to present his paper "On the Factorization of Large
Numbers." He said nothing, but demonstrated the divisors on the board
(M67 = 193707721*761838257287). It is the only presentation ever to
receive a standing ovation from the AMS members.
It is well known that there is an infinitude of prime numbers, but
there is no proof that there is an infinite number of Mersenne primes.
On to perfect numbers.
As has been previously noted, perfect numbers can be explained in terms
of the sigma function (the sum of divisors). A perfect number is one
whose divisors sum to twice the number (since it is a divisor of
itself). Alternatively, it may be defined as a number whose proper
divisors sum to itself. The early Pythagoreans were the first recorded
to know of perfect numbers.
Euclid, in book 9 of "Elements," proved that if (2^p-1) is prime, then
the product of (2^p-1) and (2^(p-1)) is perfect. Euclid showed (about
2000 years later) that every EVEN perfect number must be of this form.
(The proofs are simple and can be provided on request.) The
relationship to Mersenne primes should be obvious.
There are no known odd perfect numbers, and current belief is that none
will be found. As of 1976, using a method established by Turcaninov in
1908, a lower bound of (10^100) was known; that is, an odd perfect
number must be greater than this. A number of restrictions on odd
perfect numbers are known, but are difficult to represent in this
medium (due to superscripts and the like).
It is not known if there is an infinite number of perfect numbers.
Fermat number.
Since we're in the area, let me mention Fermat numbers. These are of
the form (2^(2^n))+1). This kind of number is a special case of
(2^k+1) which can be prime only if k is a power of 2. Fermat told
Mersenne he thought that every number of this form was prime, but Euler
showed in 1732 that F5 is not. Certainly, F0 through F4 are prime.
It is currently known that Fn is composite for 4<n<17 and some 50 or so
other values of n. However, the factors of some of these numbers are
not yet known, with F8 being the smallest (and thus most interesting)
one of these. It is not yet known is there are any other Fermat primes
beyond F4 (that I am aware).
So, why are these numbers interesting? Well, in "Disquisitiones
Arithmeticae," Gauss showed that a regular polygon with n sides is
constructible with only a ruler and compass (only straight lines and
arcs) iff n=(2^k) or n=(2^k)(p1)(p2)...(pk) where k is a non-negative
integer, and the p1, p2, ... pk are all distinct Fermat primes. Using
this, Gauss was the first one to show that a regular polygon of 17
sides could be so constructed. In fact, he requested that a 17 side
polygon be placed on his tombstone.
Furthermore, it can be easily shown that Fermat numbers are relatively
prime to each other, and this can be used to show that there is
infintely many prime numbers (since there are infinitely many Fermat
numbers).
--
Gene Spafford
School of ICS, Georgia Tech, Atlanta GA
CSNet: Spaf @ GATech ARPA: Spaf.GATech @ UDel-Relay
uucp: ...!{akgua,allegra,rlgvax,sb1,unmvax,ut-ngp,ut-sally}!gatech!spafstan@clyde.UUCP (10/24/83)
Path: clyde!akgua!emory!gatech!spaf From: spaf@gatech.UUCP Euclid, in book 9 of "Elements," proved that if (2^p-1) is prime, then the product of (2^p-1) and (2^(p-1)) is perfect. Euclid showed (about 2000 years later) that every EVEN perfect number must be of this form. ^^^^ ^^^^^ ^^^^^ (The proofs are simple and can be provided on request.) The relationship to Mersenne primes should be obvious. =-=-=-=-=-=-=-=-=-= I declare. Some people really take a long time to get around to publishing. Do you s'pose it took him that long to get his thesis done? Stan King phone: 201-386-7433 Bell Labs, Whippany, NJ Cornet: 8+232-7433 room 2A-111 uucp: clyde!stan
spaf@gatech.UUCP (10/24/83)
Oooops!! Instead of saying that Euclid showed about 2000 years later, I
should have said Euler. Sorry about that. However, if there's
anything to reincarnation, maybe I wasn't so far off.....
Also, I've been informed that F8 has been factored. I would appreciate
it if anyone who knows the factorization or source of the published
results would please post same to the net. Thanks.
--
Gene Spafford
School of ICS, Georgia Tech, Atlanta GA
CSNet: Spaf @ GATech ARPA: Spaf.GATech @ UDel-Relay
uucp: ...!{akgua,allegra,rlgvax,sb1,unmvax,ut-ngp,ut-sally}!gatech!spaf