Section19.2Conjectures and proofs

In the last section we defined some new functions, and asked some questions about them.

Remark19.2.1

Sage note:
Here is the syntax for doing this in Sage. This was a case where it was better to try it out by hand first, though!

What were some of your conjectures? Likely they included, among others, these:

\(\sigma_1(p)=p+1\) if \(p\) is prime.
\(\sigma_0(p^e)=e+1\) if \(p^e\) is a prime power.
\(\sigma_i\) is in fact multiplicative for \(i=0,1\).

They may have also included ones like this:

\(\sigma_1(p^e)=1+p+p^2+\cdots +p^e\) for \(p^e\) a prime power.
\(\sigma_1(2^e)=2^{e+1}-1\).
\(\sigma_0(n)\) is odd precisely if \(n\) is a perfect square.

Let's prove the most important of these things, as well as mention a few other useful formulas.

Subsection19.2.1Prime Powers

Usually you will discover various formulas that are special cases of the following, among others. It's surprisingly easy to find the patterns!

Fact19.2.2

If \(p^e\) is a perfect prime power, then \[\sigma_0(p^e)=e+1\text{ and }\sigma_1(p^e)=1+p+p^2+\cdots +p^e=\frac{p^{e+1}-1}{p-1}\; .\]

Proof

Subsection19.2.2Multiplicativity

It's a bit harder to prove the following.

Fact19.2.3

For any \(i\), \(\sigma_i(n)\) is multiplicative, in the sense that \[\sigma_i(mn)=\sigma_i(m)\sigma_i(n)\text{ when }gcd(m,n)=1\; .\]

This automatically leads to many facts, in particular to this one.

Theorem19.2.4

If \[n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\;\] then \[\sigma_0(n)=\prod_{i=1}^k\left(e^i+1\right)\text{ and }\sigma_1(n)=\prod_{i=1}^k\left(\frac{p_i^{e_i+1}-1}{p_i-1}\right)\; .\]

We will not prove this directly! It is possible, and might make a good challenge exercise. But it is not efficient.

Instead, we will prove a theorem that exemplifies the fact that:

In the long run, it is better to prove general lemmas for sums of arithmetic functions than to do each one by itself.

Otherwise we do an endless line of proofs like the ones we did for \(\phi\), but for every arithmetic function.

Subsection19.2.3A very powerful lemma

Let \(\sum_{d\mid n}\) denote the sum over all positive divisors (including \(1\) and \(n\)) of \(n\). Then we have the following, the proof of which will be easier than for Euler's function.

Theorem19.2.5

If \(g\) is multiplicative and \(f(n)\) is defined as \[f(n)=\sum_{d\mid n}g(d)\] then \(f\) is also multiplicative.

Proof

Corollary19.2.6

Since \(g(n)=n^i\) is clearly multiplicative, it is true that \[\sum_{d\mid n}g(d)=\sum_{d\mid n}d^i=\sigma_i(n)\] is also multiplicative.

Since we'll use them later, we put a useful pair of definitions here.

Definition19.2.7

Let us set the following two arithmetic functions:

\(u(n)=1\) to be the unit function
\(N(n)=n\) to be the identity function

These are the special cases \(i=0\) and \(i=1\) of the corollary, which show that \(\sigma_0\) and \(\sigma_1\) are multiplicative.