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$