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.
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.
- 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)= ( 2p )(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 )?
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
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.
|1||2||6||1||4th century B.C.||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|
|25||21,701||100656497054…255141605376||13,066||1978||Noll & Nickel|
|27||44,497||365093519915…353031827456||26,790||1979||Nelson & Slowinski|
|29||110,503||136204582133…233603862528||66,530||1988||Colquitt & Welsh|
|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.|