Why Perfect Numbers Only End in 6 or 8

The search for answers to simple questions like “why is the sky blue? ” and “why are there selfish acts” is a nice way to bite into a fair amount of science and philosophy, respectively. In math the same is true. Why do even-perfect numbers only end in 6 or 8? If you’re fortunate enough to have a child asking you such a question , all you need is about 1200 words to answer it—only 1/9 th of the number of words in a sitcom script. 🙂 And the discussion of perfect numbers begins with a venture into a special type of prime number.

330px-marin_mersenne
Mersenne, a priest, was a mathematician but primarily a music theorist and a hub for scientific communication in the 1600s.

As of March 2017, of all the known primes, only 49 of them are Mersenne primes. A Mersenne prime Mn can be expressed as Mn = 2p − 1, where p itself is prime. The largest prime to date is 274,207,281 − 1, known as M49. To put things into perspective, our universe only has 1080 atoms, a number with only 81 digits. But M49 has 44 677 235 digits, meaning that it is bigger than the inconceivably large 10 107. Given that the number of primes less than 10 107 is approximately equal to 10 107/log(10 107), in comparison, 49 (plus the possibly few smaller Mersennes yet to be discovered), divided by that gargantuan number is an unimaginably small fraction indeed.

  1. Why p must be prime if 2p − 1 is prime

An interesting matter is why p must be prime if 2p − 1 is prime. To convince ourselves, we will use a proof by contradiction—in other words we will make an initial assumption that states the opposite condition, logically follow it to a contradiction, and in the process reveal the assumption to be invalid.

We know from a geometric series that :

xn − 1 = (x − 1)(xn − 1 + xn − 2 + · · · + a + 1)

For example x3 – 1 = (x-1) ( x² + x  + 1)
Let’s assume that the exponent was composite, such that the Mersenne prime would be expressed as 2an – 1. In other words we assume its exponent to be composite.  Let x = 2ª. from the above geometric series; then
2an − 1 = (2ª − 1)(2ª(n − 1)+ 2ª(n − 2) + · · · + 2ª + 1)

But now we have expressed a prime number as two factors, neither of which is equal to one, which is impossible. The original assumption about p being composite was therefore false, so p must be prime.

2.  Getting a perfect number from a Mersenne Prime

Next we will multiply the Mersenne prime by a power of 2 whose exponent is one less than the prime used to generate the Mersenne prime. In other words:

(2p-1 )(2p − 1).

Interestingly this resulting number will always be a perfect number, a number that is the sum of all of its factors except itself. For example 28 is perfect because ( 23-1 )(23 − 1) = 1 + 2+ 4+7 + 14 = 28.

To reveal the “perfection” of any number of the form (2p − 1) ( 2p-1 ) where p is prime, we remind you of the function σ(x).  σ(x) is equal to the sum of all the factors of x including x. Adding a perfect number, N= ( 2p-1 )(2p − 1), to a sum that already equals N, implies that in order for a number to be perfect,

σ(N) = 2N =  2 ( 2p-1 )(2p − 1)= ( 2)(2p − 1) … (equation 1)

We start with the theorem σ(ab) = σ(a)σ(b), where a and b’s greatest common divisor =1. The reason this theorem is valid is that multiplying the sum of factors of two individual factors a and b is equivalent to getting all the non-redundant combinations of the product’s factors. For example, consider ab = 12 where σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28. That is equivalent to doing the following : σ(4)σ(3) = ( 1 + 2 + 4)(1 + 3) = 1(1) + 1(2) + 1(3) +2(3) + 4(1) +4(3) = 28.

Applying the theorem to our expression:

 σ[( 2p-1 )(2p − 1)] = σ( 2p-1 ) ∗ σ(2p − 1).                    … equation (2)

Beginning with σ( 2p-1 ), we have here simply the sum of the factors of a power of two up to that power. σ( 2p-1 ) = 20 + 21 + 22 + 23 + …..2p-2 + 2p-1

We add 1 to each side:

1+ σ( 2p-1 ) =( 1 + 20 )+ 21 + 22 + 23 + …..2p-2 + 2p-1

We notice that the first terms’ sum is equal to the next power such that:

1+ σ( 2p-1 ) = (21  + 21 )+ 22 + 23 + …..2p-2 + 2p-1 But this keeps happening:

1+ σ( 2p-1 ) = (22  + 22 )+ 23 + …..2p-2 + 2p-1 When we get to the second last term, we will have

1+ σ( 2p-1 ) = (2p-2 +2p-2 )+ 2p-1.

1+ σ( 2p-1 ) = (2p-1 )+ 2p-1 =  2p ,

or σ( 2p-1 ) = 2p – 1                                                       ……equation (2b)

We substitute this result into equation (2) and obtain

 σ[ ( 2p-1 )(2p − 1)] = (2p – 1 ) * σ(2p − 1).                          … equation(3)

But σ(2p − 1) is the sum of the factors of a prime number which means that we merely have to add 1 to itself = 1 + 2p − 1 = 2p . 

Substituting this result into equation (3) we obtain:

 σ[( 2p-1 )(2p − 1)] = (2p – 1 )2p , which meets the condition we had outlined for a perfect number in equation (1)!

3. Why multiply a Mersenne by ( 2p-1 )?

sum_numbertheory
A derivation of S = n(n+1)/2

But where does the idea of multiplying a Mersenne prime (2p − 1) by ( 2p-1 ) come from? To get the sum, S,  of all the natural numbers from 1 to 100 in other words (1 + 2+ 3+ 4 ….100), we simply multiply the largest number by the next natural number and divide by 2, so S(100) = 100*101/2 = 5050. The formula is S(n)= n(n+1)/2 and I derived it informally and partly pictorially in the adjacent drawing.

Applying the formula to the Mersenne prime we get (2p − 1)(2p − 1 + 1)/2 = (2p − 1)(2p)/2¹ = (2p − 1)(2p-1)

4. But does an even perfect number have to be of the form (2p − 1)(2p-1) ?

The answer is yes, and here is my summary of a clearer version of the Euclid-Euler Theorem found here.  Let the even perfect number = 2k  *a, where a is an odd number.

As seen earlier, if the number is perfect then

σ(2k *a) = σ(2k) σ(a) , which applies since a power of 2 and an odd number will never have a common factor greater than 1

As we demonstrated to get to equation 2(b), the sum of the factors of a power of 2 is equal to the next power of 2 minus 1, so

σ(2k  *a) = 2k+1 -1 * σ(a).                                                   ….equation (4)

Since 2k  *a is perfect, the sum of all of its factors will also equal twice itself, so:

σ(2k  *a) = 2*2k  *a = 2k+1 *a                                                  …equation (5)

Equating equations (4) and (5) we obtain,

(2k+1 -1)* σ(a) =  2k+1 *a                                                         …equation (6)

or rearranging  σ(a) = 2k+1 *a /(2k+1 -1)

We can see from this expression  that σ(a) is the product of 2k+1 and another expression which we’ll simplify as b.

so σ(a) = 2k+1 *b         , where b = a/ (2k+1 -1)                …equation (7)

Rearranging the expression for b,

a = (2k+1 -1) * b and

σ(a) = σ( (2k+1 -1) * b)                                                               …..equation (8)

From equation (7)

σ(a) = 2k+1  *b , which we can rewrite as σ(a) =2k+1  *b -b + b . If we then factor the first two terms to get:

σ(a) = b(2k+1   -1) + b .                                                                  ….equation (9)

Equating (8) and (9):

σ( (2k+1 -1) * b)   =  b(2k+1   -1) + b .     The only way that the factors of  (2k+1 -1) * b  won’t exceed the discovered sum of  b(2k+1   -1) + b is if b =1, so our original odd number a only has two factors, one of which is 1,  revealing that a is prime. Moreover a is a Mersenne prime since it is of the form 2k+1 – 1

cavalieri
A contemporary of Mersenne, Pietro Cataldi discovered that perfect numbers end in either 6 or 8.

7. Finally we return to the question in the title. Why do all even perfect numbers (no one yet found an odd-numbered one ) have to end in 6 or 8?

A perfect number = ( 2p-1 )(2p − 1). The first factor of that expression,  2p-1 , will always create an even power of 2, except for 22-1 which will still satisfy our overall generalisation by creating 6. All even powers of 2 end either with the digit 6 or 4. The next power 2p , which follows 2p-1 , ends in either 2 or 8, respectively. But we subtract 1 from each of those numbers because we are multiplying ( 2p-1 ) by (2p − 1). That translates into either multiplying a number ending in 6 by (1=2-1), which will end in 6 or a number ending in 4 by (7= 8-1), whose result will end in 8.

Here’s a table from Wikipedia of all known perfect numbers as of March 4, 2017. To date, thirty of the discovered perfect numbers end in 6 and nineteen end in 8.

Rank p Perfect number Digits Year Discoverer
1 2 6 1 4th century B.C.[5] Euclid
2 3 28 2 4th century B.C. Euclid
3 5 496 3 4th century B.C. Euclid
4 7 8128 4 4th century B.C. Euclid
5 13 33,550,336 8 1456 First seen in a medieval manuscript, Munich, Bayerische Staatsbibliothek, CLM 14908, fol. 33[6]
6 17 8,589,869,056 10 1588 Cataldi[1]
7 19 137,438,691,328 12 1588 Cataldi[1]
8 31 2,305,843,008,139,952,128 19 1772 Euler
9 61 265845599156…615953842176 37 1883 Pervushin
10 89 191561942608…321548169216 54 1911 Powers
11 107 131640364585…117783728128 65 1914 Powers
12 127 144740111546…131199152128 77 1876 Lucas
13 521 235627234572…160555646976 314 1952 Robinson
14 607 141053783706…759537328128 366 1952 Robinson
15 1,279 541625262843…764984291328 770 1952 Robinson
16 2,203 108925835505…834453782528 1,327 1952 Robinson
17 2,281 994970543370…675139915776 1,373 1952 Robinson
18 3,217 335708321319…332628525056 1,937 1957 Riesel
19 4,253 182017490401…437133377536 2,561 1961 Hurwitz
20 4,423 407672717110…642912534528 2,663 1961 Hurwitz
21 9,689 114347317530…558429577216 5,834 1963 Gillies
22 9,941 598885496387…324073496576 5,985 1963 Gillies
23 11,213 395961321281…702691086336 6,751 1963 Gillies
24 19,937 931144559095…790271942656 12,003 1971 Tuckerman
25 21,701 100656497054…255141605376 13,066 1978 Noll & Nickel
26 23,209 811537765823…603941666816 13,973 1979 Noll
27 44,497 365093519915…353031827456 26,790 1979 Nelson & Slowinski
28 86,243 144145836177…957360406528 51,924 1982 Slowinski
29 110,503 136204582133…233603862528 66,530 1988 Colquitt & Welsh
30 132,049 131451295454…491774550016 79,502 1983 Slowinski
31 216,091 278327459220…416840880128 130,100 1985 Slowinski
32 756,839 151616570220…600565731328 455,663 1992 Slowinski & Gage
33 859,433 838488226750…540416167936 517,430 1994 Slowinski & Gage
34 1,257,787 849732889343…028118704128 757,263 1996 Slowinski & Gage
35 1,398,269 331882354881…017723375616 841,842 1996 Armengaud, Woltman, et al.
36 2,976,221 194276425328…724174462976 1,791,864 1997 Spence, Woltman, et al.
37 3,021,377 811686848628…573022457856 1,819,050 1998 Clarkson, Woltman, Kurowski, et al.
38 6,972,593 955176030521…475123572736 4,197,919 1999 Hajratwala, Woltman, Kurowski, et al.
39 13,466,917 427764159021…460863021056 8,107,892 2001 Cameron, Woltman, Kurowski, et al.
40 20,996,011 793508909365…578206896128 12,640,858 2003 Shafer, Woltman, Kurowski, et al.
41 24,036,583 448233026179…460572950528 14,471,465 2004 Findley, Woltman, Kurowski, et al.
42 25,964,951 746209841900…874791088128 15,632,458 2005 Nowak, Woltman, Kurowski, et al.
43 30,402,457 497437765459…536164704256 18,304,103 2005 Cooper, Boone, Woltman, Kurowski, et al.
44 32,582,657 775946855336…476577120256 19,616,714 2006 Cooper, Boone, Woltman, Kurowski, et al.
45 37,156,667 204534225534…975074480128 22,370,543 2008 Elvenich, Woltman, Kurowski, et al.
46 42,643,801 144285057960…837377253376 25,674,127 2009 Strindmo, Woltman, Kurowski, et al.
47 43,112,609 500767156849…221145378816 25,956,377 2008 Smith, Woltman, Kurowski, et al.
48 57,885,161 169296395301…626270130176 34,850,340 2013 Cooper, Woltman, Kurowski, et al.
49 74,207,281 451129962706…557930315776 44,677,235 2016 Cooper, Woltman, Kurowski, Blosser, et al.
perfectnumbers
The cover and an extract from Cataldi’s treatise on perfect numbers. The entire original is found at http://mathematica.sns.it/media/volumi/69/Trattato%20de’%20numeri%20perfetti_bw_.pdf
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s