13 April 2006
The Perfect numbers: The Trace of the Hunt down
“Six is a number perfect in itself,
And not just because
God created all things in 6 days;
Rather the converse is true.
God created all things in six days
Because the number six is perfect.”
--St Augustine, “The City of God”
1. Early history
Perfect numbers has always been a fascinating subject to mathematics.
Many ancient cultures were concerned with the relationship of a number with the sum of its divisors, often giving mystic interpretations. Either it is symbolic and realistic. It is not known when perfect numbers were first studied and indeed the first studies may go back to the earliest times when numbers first aroused curiosity.
Nicomachus of Gerasa who wrote his well-known text Intoductio Arithmetica in 100AD conducted the opening significant study of Perfect Numbers.
He divided numbers into three different classes:
1. Superabundant – the summation of the number’s aliquot parts is greater than the number.
2. Deficient – the addition of the numbers aliquot parts is less than the number.
3. Perfect Numbers – the sum of the numbers aliquot parts is equal to number.
(An aliquot part (or simply aliquot), in the context of mathematics, is an integer that is an exact divisor of a quantity. For instance, 2 is an aliquot of 12. The sum of all the aliquots of a quantity is referred to as the divisor function on that quantity, denoted σ(n).)
Based on observation of first four perfect numbers, Nicomachus pointed out these certain results. They are:
1. The n-th Perfect Number has n digits.
2. All perfect numbers end in 6 and 8 alternately.
3. All perfect numbers are even.
4. Euclid’s Algorithm to generate Perfect Numbers will give all perfect numbers.
5. There are infinitely many Perfect numbers.
It is thought that these five statements are not anchored in anything more prolific than Euclid’s algorithm. Nicomachus’ assertions were used as fact for numerous years even thought it was not justified.
At one point of the history, there arose a religious significance of Perfect numbers that, six is perfect because god took six days to create the world, 28 as that is the number of days for one full orbit of the moon.
In Europe around 1500s at the time of the mathematical renaissance it was still thought that Nicomachus’ assertions were true, nothing further having been discovered. Some still blindly believed that 2k-1(2k-1) gives a Perfect Number for all odd integers k.
First four perfect numbers were discovered early during the Nicomachus’ time (6, 28, 496, and 8128). In 13th century Arab Ibn Fallus claimed to have found first 10 perfect Numbers. However, the first seven of which turned out to be true but the last three were not (33550336, 8583869056, 13743869056, 2305843008139952128, etc).
Unfortunately these results went unnoticed by the European Mathematics world and were not rediscovered until mid 15th century by Regiomentanus during his stay at the University of Vienna which he left in 1461.
It was believed that (2^p-1)(2^p-1) is perfect for every p – prime number.
In 1539, Huldanchus Regius made the first break through that was to become common knowledge to later mathematicians. He published Utriusque Arithmetices in which he gave the factorization 2^11-1= 2047 = 23*89. With which he showed that the first prime p such that (2^p-1)*(2^p-1) is not a Perfect Number. He also showed that 2^13-1= 8191 is prime so he had discovered (and made it known) that the fifth perfect number 2^12*(2^13-1) =33550336. This showed a contradiction to Nichamachus’ first assertion since the fifth perfect number had 8 digits. The claim that the perfect numbers end in 6 and 8 alternately still stood however. Even with this mathematical breakthrough in terms of perfect numbers Regius is virtually unheard today.
Cataldi in Europe rediscovered the sixth perfect number in 1603. It was namely, 2^16*(2^17-1) = 8589869056 so that one of the Nichamachus’ assertion was wrong.
Mersenne made the next major contribution. He alleged that 2p-1 is prime (and so 2p-1(2p-1) is a Perfect number) for: p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 and for no other value of p<257
In 1732, Euler proved the eighth Perfect number was 2^30*(2^31-1) = 23054300813995218. it was the first time in 125 years that a Perfect Number had been rediscovered. In 1738, he also disproved the last of Cataldi’s claims when he proved 2^29-1 was not a prime. Euler also tried to explore existence of odd perfect Numbers. He managed to prove that any odd Perfect Number had to have a form: (4n+1)^(4k+1)*(b^2) where (4n+1) is prime.
2. Research on Perfect numbers
Definition: 1. A positive integer n is called a perfect number if it is equal to the sum of all its positive divisors, excluding n itself.
2. When 2^n-1 is prime then it is said to be a Mersenne prime.
As we observe the known perfect numbers, they all have the same form 2n-1(2n-1). That in each case 2n-1 was a Mersenne prime. In fact, it is easy to demonstrate the following theorems.
If 2k-1 is a prime number, then 2k-1(2k-1) is a perfect number and every even known perfect number has this form.
Proof: Suppose first that p = 2k-1 is a prime number, and set n = 2k-1(2k-1). To show n is perfect we need only show sigma(n)= 2n. Since sigma is multiplicative and sigma(p) = p+1 = 2k, we know
sigma(n) = sigma(2k-1).sigma(p) = (2k-1)2k = 2n.
This shows that n is a perfect number.
On the other hand, suppose n is any even perfect number and write n as 2k-1m where m is an odd integer and k>2. Again sigma is multiplicative so
sigma(2k-1m) = sigma(2k-1).sigma(m) = (2k-1).sigma(m).
Since n is perfect we also know that
sigma(n) = 2n = 2km.
Together these two criteria give
2km = (2k-1).sigma(m),
so 2k-1 divides 2km hence 2k-1 divides m, say m = (2k-1)M. Now substitute this back into the equation above and divide by 2k-1 to get 2kM = sigma(m). Since m and M are both divisors of m we know that
2kM = sigma(m) > m + M = 2kM,
So sigma(m) = m + M. This means that m is prime and its only two divisors are itself (m) and one (M). Thus m = 2k-1 is a prime and we have prove that the number n has the prescribed form.
If for some positive integer n, 2n-1 is prime, then so is n.
Let r and s be positive integers, then the polynomial xrs-1 is xs-1 times xs(r-1) + xs(r-2) + ... + xs + 1. So if n is composite (say r.s with 1<s<n), then 2n-1 is also composite (because it is divisible by 2s-1).
Notice that we can say more: suppose n>1. Since x-1 divides xn-1, for the latter to be prime the former must be one. This gives the following.
Let a and n be integers greater than one. If an-1 is prime, then a is 2 and n is prime.
Usually the first step in factoring numbers of the forms an-1 (where a and n are positive integers) is to factor the polynomial xn-1. In this proof we just used the most basic of such factorization rules.
Let p and q be odd primes. If p divides Mq, then p = 1 (mod q) and p = +/-1 (mod
If p divides Mq, then 2q = 1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q. By Fermat's Little Theorem the order of 2 also divides p-1, so p-1 = 2kq. This gives
2(p-1)/2 = 2qk = 1 (mod p)
So 2 is a quadratic residue mod p and it follows p = +/-1 (mod
, which completes the proof.
Let p = 3 (mod 4) be prime. 2p+1 is also prime number if and only if 2p+1 divides Mp.
Suppose q = 2p+1 is prime. q = 7 (mod
so 2 is a quadratic residue modulo q and it follows that there is an integer n such that n2 = 2 (mod q). This shows
2p = 2(q-1)/2 = nq-1 = 1 (mod q),
Showing q divides Mp.
Conversely, let 2p+1 be a factor of Mp. Suppose, for proof by contradiction, that 2p+1 is composite and let q be its least prime factor. Then 2p = 1 (mod q) and the order of 2 modulo q divides both p and q-1, hence p divides q-1. This shows q > p and it follows
(2p+1) + 1 > q2 > p2
This is a contradiction since p > 2.
If you sum the digits of any even perfect number (except 6), then sum the digits of the resulting number, and repeat this process until you get a single digit, that digit will be one.
Let s(n) be the sum of the digits of n. It is easy to see that s(n) = n (mod 9). So to prove the theorem, we need only show that perfect numbers are congruent to one modulo nine. If n is a perfect number, then n has the form 2p-1(2p-1) where p is prime. So p is either 2, 3, or is congruent to 1 or 5 modulo 6. Note that we have excluded the case p=2 (n=6). Finally, modulo nine, the powers of 2 repeat with period 6 (that is, 26 = 1 (mod 9)), so modulo nine n is congruent to one of the three numbers 21-1(21-1), 23-1(23-1), or 25-1(25-1), which is all 1 (mod 9).
The knowledge of the Perfect numbers became widespread and vast, but yet to be known completely. We do not know how many perfect numbers there are but we do know that there are an infinite number of prime numbers, which means there is a very high chance that there are an infinite Mersenne primes (see Theorem 1).
Nowadays finding a Perfect number became a big computing project. There are special ways to compute perfect numbers but mainly Lucas-Lehmer Test is used.
Lucas-Lehmer Test: For p an odd prime, the Mersenne number 2p-1 is prime if and only if 2p-1divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4.
The theory for this test was initiated by Lucas in 1870’s and then made into this simple test about 1930 by Lehmer. The sequence S(n) is computed modulo 2p-1 to save time. This test is ideal for binary computers because the division by 2p-1 (in binary) can be done using rotation and addition only.
So far, according to the Mersenne organization, there are 43 known Mersenne prime numbers. This indicates that there are 43 known “perfect” numbers. On December 15, 2005, Dr. Curtis Cooper and Dr. Steven Boone, professors at Central Missouri State University, discovered the 43rd Mersenne Prime, 230,402,457-1. The new prime is 9,152,052 digits long. This means the Electronic Frontier Foundation $100,000 award for the discovery of the first 10 million digit prime is still up for grabs! The new prime was independently verified in 5 days by Tony Reix of Bull S.A. in Grenoble, France using 16 Itanium2 1.5 GHz CPUs of a Bull NovaScale 6160 HPC at Bull Grenoble Research Center, running the Glucas program by Guillermo Ballester Valor of Granada, Spain.
Let M(p) = 2p-1 and P(p) = 2p-1(2p-1). The list of all known primes p for which M(p) is a Mersenne prime (therefore P(p) is a perfect number) follows:
n-th “p exponent” “digits in Mp” “digits in Pp” “year” “discoverer”
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
4 7 3 4 ---- ----
5 13 4 8 1456 anonymous
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers note
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
19 4253 1281 2561 1961 Hurwitz
20 4423 1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll "
27 44497 13395 26790 1979 Nelson & Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 216091 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski & Gage et al.
33 859433 258716 517430 1994 Slowinski & Gage
34 1257787 378632 757263 1996 Slowinski & Gage
35 1398269 420921 841842 1996 Armengaud, Woltman,
36 2976221 895932 1791864 1997 Spence, Woltman,
37 3021377 909526 1819050 1998 Clarkson, Woltman,
38 6972593 2098960 4197919 1999 Hajratwala, Woltman,
?? 13466917 4053946 8107892 2001 Cameron, Woltman,
?? 20996011 6320430 12640858 2003 Shafer, Woltman, Kurowski
?? 24036583 7235733 14471465 2004 Findley, Woltman, Kurowski
?? 25964951 7816230 15632458 2005 Nowak, Woltman, Kurowski
?? 30402457 9152052 18304103 2005 Cooper, Boone, Woltman,
Pursue of finding an even perfect number is almost done. Human attempt to find an even perfect numbers approached the limit. We just have to leave it to computers. However, the trace of hunting an odd perfect number remained breathing. We don’t know the existence of an odd perfect number yet. According to all the attempts of exploration of an odd perfect number, it remained mystery forever. Throughout the history, great mathematicians have struggled to solve the mystery for three thousand years. Great mathematicians are trying to disprove the existence of an odd perfect number. It’s assured by computing that there is no perfect odd number exists between 1 to 10300 . So will this trace become a hunt with computers or a natural proof with human intellect? The pursue passes on to the young minds like yours.