Saturday, December 07, 2019

Books: Math Recreations (Kraitchik) Part 5

I have more old math books than I'll ever read or need. This is just a fact. I would collect them, and sometimes read through parts of them, but never finish any of them. ...

Day 5: Fermat Numbers, Mersenne Primes and Perfect Numbers

Following up to Thursday's entry in this series:

A few final thoughts on this chapter, and then I'll move on.


Fermat Numbers:

I don't think I actually knew what these were. Fermat concluded that numbers in the form 2k + 1, were prime when k was a power of 2. (Read below)
This could also be written as 22**n + 1, where n is a natural number and ** means exponent -- my HTML doesn't allow for exponents of exponents.

The reasoning why the exponents had to be powers of 2 is because k could not have any odd exponents. If k had an odd factor, it could be written as m n, where n was odd.

But we know that we can divide (xm n + 1) by (xm + 1) resulting in xmn - m - xmn - 2m + ... + 1
If that isn't readable, if one factor of the exponent is odd, the expression can be factored (or divided) by one more than x raised to the other factor. (In this case, x = 2.) The result of the division doesn't really matter, as long as we know it's an integer and the original number was composite.

Unfortunately for Fermat, he was wrong about his conclusion, although the first few Fermat Numbers are prime. Euler proved 2^32 + 1 could be factored, and other numbers have been tested now that computers make it easy. (As of the printing of the book, the factorization of many of these numbers is unknown -- only the fact that it isn't prime is known.)


Mersenne Primes and Perfect Numbers

Mersenne primes, I'm familiar with. I even did a comic a long time ago, back in 2008.

Mersenne primes are those that can be written in the form 2n - 1. It doesn't work for all values of n, of course. In fact, they are quite rare, and the search for these primes continues. Since the comic above was created, at least two more have been found.

But we can eliminate many exponents. For example, if n is even, that 2n - 1 can be factored with the Difference of Squares Rule into (2n/2 + 1)(2n/2 - 1). (the exception being 2 itself, because (2 - 1) is a factor of 1.) And if n is composite, then it can be factored similar to the Fermat numbers above, with a similar looking result (except the minus signs will all be addition instead).

So the exponent needs to be prime, and can be written as 2p - 1.

Nothing more needs to be said here. I just wanted the introduction so I could talk about Perfect Numbers. Perfect Numbers are numbers where the sum of all the factors, excluding the number itself, is that number. Example, 1 + 2 + 3 = 6 and 1 + 2 + 4 + 7 + 14 = 28, but 1 + 2 + 3 + 4 + 6 =/= 12.

Again, these are numbers I knew about long, long ago, even before I knew about Mersenne primes, which is why the following formula was such a revelation to me the first time I saw it:

(2n - 1)(2n - 1)

Can we stop and just admire the beauty of this expression.

I learned sometime ago (maybe from reading through this book once before) that Perfect Numbers were always a multiple of a Mersenne prime. That is itself seemed an odd co-incidence. But if you write it out, you see that the other factor is almost the same thing algebraically -- it's the same value of n. The only difference is the placement of the "- 1".

To be sure, this formula does NOT produce perfect numbers for all values of n, BUT as of right now, all known perfect numbers fit that expression. This means that all of the known perfect numbers are, in fact, even. Are there odd perfect numbers? Right now, it is not known, but this formula seems so ... perfect ... that I doubt one will be found.

Stuff like this make math awesome.

No comments:

Post a Comment