Forever ago, Euclid proved that any positive integer of the form
$(2^{k-1})(2^{k}-1)$
Will be a perfect number so long as $2^{k}-1$ is prime (primes that are one less than a power of two are called Mersenne Primes).
In the 1700s, Euler proved that all even perfect numbers will be of this form.
If you're interested, you can read their proofs on Wikipedia. You will notice that they're very concise and do a good job showing that this is true, but (at least for me) do not leave you with a good intuition why this should be true.
So let me see if I can help with that!
Recall that a perfect number is a positive integer whose factors (including itself) add up to double itself. For example, $6$ is a perfect number since the factors of $6$ are $1, 2, 3, 6$. If you add up all the factors, you get $12$ which is double $6$ and therefore $6$ is a perfect number.
This is an illustration emphasizing the role that the factors $2^{k-1}$ and $2^{k}-1$ play in the makeup of $6$. Note that in this case, $k=2$.
I have drawn it again, but this time I have replaced the three blocks that represent $2^{k}-1$ with one bigger block that says $3$. And notice that there are $2$ of these blocks. This is because
$2^{2-1} = 2^{1} = 2$
So essentially what we've done so far is draw the number $(2^{k-1})(2^{k}-1)$ chopped up into its factors of $2^{k}-1$. And if $6$ is a perfect number (which it is) then if we continue drawing its factors then they should all add up to be twice as much as what we've drawn so far.
The $\sigma$ function simply means that we will add up all of the factors of the input. The illustration shows the "goal" that we're trying to get to. We want to show that $6$ is a perfect number by showing that it's factors add up to $2 \cdot 6$.
The first row was easy to derive, because that's just $6$, and of course $6$ is a factor of itself. Well, $6$ is divisible by $2$. So let's chop $6$ in half and add that to the next row. Notice we're still missing a chunk from our picture that we need in order to show that $6$ is perfect.
We have an easy way to find the remaining factors! Let's pause and think about what we've done so far.
We started with $2 \cdot 3$ which we get from $(2^{k-1})(2^{k}-1)$ when $k=2$. So $3$ functions as our prime number and the first row has $2^{k-1}$ many $3$s. It worked nicely to get the second row since $6$ is divisible by $2$. But, this was no coincidence, because $2^{k-1}$ is a power of $2$ we can always produce $k-1$ rows by repeatedly halving the original number. In this case, $k-1=1$ so we only divide by $2$ once and we're left with $2$ rows, but soon you will see this works nicely for larger perfect numbers too.
So we start with the factor $6$ then divide by $2$ to get the factor $3$. And as the image above illustrates, we can find the remaining factors by checking what we need to multiply each row by to get back to $6$. In this case, those factors are $1$ and $2$. So let's add that to the image.
And this is the super cool part! Since $3$ is a prime number (and for this proof to be valid, $2^{k}-1$ will always be prime) then we know its only factors are $3$ and $1$, which are both already accounted for. This is important, because this means that we will always $\sigma(2^{k-1})$ "big blocks" on the top, since each big block is $2^{k}-1$. Also,
$\sigma(2^{k-1}) = 2^{k}-1$
which has a simple proof by induction that I show in my previous post.
This is crucial! We have $2^{k}-1$ big blocks, each of which represent the value $2^{k}-1$.
And we will also have $2^{k}-1$ small blocks (which each represent $1$). We start with the first row of big blocks that represents our original number, which corresponds with the "small block" factor of $1$ since
$1 \cdot (2^{k-1})(2^{k}-1) = (2^{k-1})(2^{k}-1)$
The next row we got by dividing the first row in two. This corresponds with the "small block" factor of $2$ since
$2 \cdot \frac{(2^{k-1})(2^{k}-1)}{2} = (2^{k-1})(2^{k}-1)$
And this pattern continues, making the total number of small blocks:
$1 + 2 + ... + 2^{k-1}$
And this is exactly the factors of $2^{k-1}$, so as already pointed out, this means:
$1 + 2 + ... + 2^{k-1} = \sigma(2^{k-1}) = 2^{k}-1$
So now we have $2^{k}-1$ small blocks, which add up to exactly one big block!
Then we now have $2^{k}-1 + 1$ big blocks, which is $2^{k}$. Each big block represents the value $2^{k}-1$. So in total we have:
$(2^{k})(2^{k}-1) = 2 \cdot (2^{k-1})(2^{k}-1)$
Then that means the factors of $(2^{k-1})(2^{k}-1)$ add up to $2 \cdot (2^{k-1})(2^{k}-1)$ which is the definition of a perfect number!
I will do one more example using $28$ as the perfect number, which may help solidify this explanation.
We start by dividing up $28$ into $2^{k-1}$ equal big blocks, each of which have value $2^{k}-1$. Then we find all $k-1$ rows by halving the previous row.
By the same reasoning as last time, we know we have $2^{k}-1$ small blocks:
Then these small blocks all form one big block:
And these big blocks are guaranteed to add up to twice the original amount:
And to reiterate, the importance that $2^{k}-1$ is prime is that this makes sure there are no other "little block" factors, other than the $2^{k}-1$ that we already got. Then the little blocks will always add to one big block, hence allowing all the factors to add up to twice the value of the perfect number.
This was very hard to explain in writing but I hope it's coherent!
No comments:
Post a Comment