Euclid-Euler Theorem Proved Visually

Update: I made an animated version of this same proof which I believe is easier to follow than the written version. You can view it on my YouTube channel.

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!

Proof Sum of Divisors Function is Multiplicative

I was reading the Wikipedia article on the Euclid-Euler theorem and in the proof section, two truths are mentioned that are necessary for Euler's proof, but neither are proved themselves.

I decided to prove both of these statements as an exercise and so that I may better understand Euler's proof.

The first of two statements is the following:

"Euler's proof is short and depends on the fact that the sum of divisors function $\sigma$ is multiplicative; that is, if $a$ and $b$ are any two relatively prime integers, then $\sigma(ab) = \sigma(a)\sigma(b)$."

 The sum of divisors function $\sigma$ sums all factors of its input. For example,

$\sigma(6) = 1 + 2 + 3 + 6 = 12$

The numbers summing to $12$ are all the positive integers that divide $6$.

Let $a$ and $b$ be two co-prime integers. Then we have:

$\sigma(a) = 1 + a_1 + a_2 + ... + a_n$
$\sigma(b) = 1 + b_1 + b_2 + ... + b_n$

Where $a_i$ and $b_i$ represents the factors besides $1$ (for prime numbers, there will be no other factors). Now I will define two new variables:

$A = \sigma(a) - 1$
$B = \sigma(b) - 1$

$A$ represents all of the factors of $a$ that are not factors of $b$ and vice versa. Since $a$ and $b$ are co-prime, we only need to subtract one from each since that's the only factor they share.

Now consider the product $ab$. What will its factors be? Well, it will inherit all the factors of $a$ and all the factors of $b$ since anything that can divide $a$ can also divide $ab$. Also $ab$ will be divisible by the product $a_i b_i$ which is any factor from $a$ times any factor from $b$.

Thanks to the distributive rules of multiplication, we can express the sum of all factors of $ab$ that can be expressed as $a_i b_i$ by the product:

$AB = (a_1 + a_2 + ... + a_n)(b_1 + b_2 + ... + b_n)$
$= a_1 b_1 + a_1 b_2 + ... + a_1 b_n\\
+ a_2 b_1 + a_2 b_2 + ... + a_2 b_n\\
+ ...\\
+ a_n b_1 + a_n b_2 + ... + a_n b_n$

This will result in every product between the factors of $a$ and $b$ except $1$, then we sum them together.

And now we have all the information we need! Consider:

$\sigma(ab) = 1 + A + B + AB$

This must be true, since we account for all factors of $ab$ and we sum them together, following the definition of the $\sigma$ function. And expressing it in this form makes it obvious that:

$\sigma(a)\sigma(b) = (1 + A)(1 + B) = 1 + A + B + AB = \sigma(ab)$

And so the $\sigma$ function is multiplicative.



The second statement that the Wikipedia article mentions is the following:

"The sum of divisors for $2^{p − 1}$ is $2^{p} − 1$, e.g. for $p=5$ we get $16$ $(2^{5 − 1})$ and the sum of its divisors is $31$ $(1 + 2 + 4 + 8 + 16 = 31 = 2^{p} − 1)$."

In the article, $p$ is any prime number, however for this particular statement it's not necessary that $p$ be prime, as you will see.

Consider the number $2^{p}$. Conveniently, this number is already in the form of its prime-factorization since $2$ is a prime number. We can easily convert a prime factorization of a number into its normal factorization by multiplying together every combination of its prime factors.

In this case we get:

$2^{0}, 2^{1}, 2^{2}, ... , 2^{p} = 1, 2, 4, ... , 2^{p}$

Now let's take the sum of all the factors:

$\sigma(2^{p}) = 1 + 2 + 4 + ... + 2^{p}$

Notice that:

$\sigma(2^{0}) = 2^{1} - 1$

So then we know for at least one value of $k$ it's true that:

$\sigma(2^{k-1}) = 1 + 2 + 4 + ... + 2^{k-1} = 2^{k} - 1$

Then with that assumption we can prove that it's true for $k + 1$

$\sigma(2^{k})  = 1 + 2 + 4 + ... + 2^{k-1} + 2^{k}$
$= (2^{k} - 1) + 2^{k}$
$= 2(2^{k}) - 1$
$= 2^{k+1} - 1$

Then it's true for all integers $p \geq 0$ that $\sigma(2^{p-1}) = 2^{p} - 1$

The Sum of Cubes and the Triangle Numbers

Update: I created an animated version of this same proof. Check it out on my YouTube channel!

Earlier today I came across the summation:

$\sqrt{1^3 + 2^3 + ... + n^3}$

After calculating the sum for some low values of $n$, it seemed as though this summation was exactly equivalent to the following:

$1 + 2 + ... + n$

The latter summation is the definition of the $n$th triangle number. In other words, the triangle number of the positive integer $n$ is the sum of all positive integers less than or equal to $n$.

I was very perplexed to see this, and needed some proof and reasoning of why this should be true.

And this is where it gets fun!

Let us first see how this is true geometrically for small values of $n$, then we can generalize from there.

Consider the following image:

We start off with one cube (right). Now let us see if we can arrange it into a square (left). Imagine the square view is just viewing the cube from the top down.

Alright, that was easy. Since $1$ is a perfect square, we can take its square root and get an integer value, showing that

$\sqrt{1^3} = 1$

which so far is consistent with the triangle numbers, since the first triangle number is also $1$. Don't worry if this doesn't make sense yet, because we haven't really done anything.

Let's make things a little more interesting by looking at the summation for $n=2$

The left view represents the sum so far. We started with $1^3$ which is simply $1$ so we've drawn one box to left. Now we must add $2^3$ which is picture to the right. To visualize this I will start by moving only one layer of the cube over to the left.

And now it's pretty apparent that we can move the remaining $4$ cubes over to the left side to make another perfect square.

Great! Our assumption that the square root of the sum of cubes is equivalent to the triangle numbers still holds, because

$\sqrt{1^3 + 2^3} = 1 + 2 = 3$

Now we're ready to generalize this, so we can know that this is true for any positive integer $n$.

Once again, the left view represents the sum so far (which we know is a perfect square), and the right view represents the $n$th cube that we're adding.

We always start by adding only one layer of the cube to our sum. Notice that every layer of $n^3$ is composed of exactly $n^2$ unit cubes. This means that there are $n^3 - n^2$ remaining unit cubes on the right that we somehow need to fit into the square on the left. We've done it for $n=1$ and $n=2$ but now we must find a way to prove we can make a perfect square for any positive integer $n$.

I notice that there are two rectangles missing from the square. One side length is simply $n$ since that's the side length of the square we've just added. The other side length is the sum of the side lengths of all the previous cubes we've added. In other words, it's the triangle number of $n-1$. We can be sure of this, since we always construct the next perfect square by placing one layer of the cube diagonally, insuring that each side length of the square increases by the side length of the cube.

And in fact, there's a cool trick for deriving an equation for the $n$th triangle number. Consider:

This schematic demonstrates adding up the numbers from $1$ to $n$ to calculate the $n$th triangle number. Nothing too special. But, if we double that triangle we made and rotate it...

Amazing! We've made a rectangle that we know has the area of twice the $n$th triangle number. So we can just divide the area by $2$ and we get the equation:

$\frac{n(n+1)}{2}$

And what we actually need is the triangle number for $n-1$, which comes out to be:

$\frac{n(n-1)}{2}$

And with that, we've found the area of the missing rectangles!

Notice that the area of both missing rectangles combined is $n^3 - n^2$ which is exactly the remaining number of unit cubes on the right! This means we know we can make a perfect square for any value of $n$. And what's more, we know the side length of the perfect square is the $n$th triangle number, thanks to our sneaky method of constructing the perfect square starting with one layer of the cube.

This shows that the square root of the sum of the first $n$ cubes is in fact equivalent to the $n$th triangle number! Wow, I love math.

I would not be surprised if this proof has been shown elsewhere, but I did discover this proof independently and had fun doing it! Now time to sleep.