NTIC Conjectures and Proofs

Section 19.2 Conjectures and Proofs

Remark 19.2.1.

Don't read this section until you have tried some of the exploration in the previous section!

In the last section we defined some new functions, and asked some questions about them. You can try them by hand, or use computation to explore them further.

Sage note 19.2.2. Syntax for sigma.

Here is the syntax for doing this in Sage. However, for this function it is better to try it out by hand first!

If you do not put the second argument in, Sage just computes \(\sigma_1=\sigma\) by default.

What were some of your conjectures? It is quite likely that you (or others, if in a class setting) discovered some of 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\text{.}\)

If you dug a little deeper, or had a little more time to spend, your conjectures may have also included some like these:

\(\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\text{.}\)
\(\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.

Subsection 19.2.1 Prime powers

Again, usually one will have discovered various formulas that are special cases of the following, among others. It's surprisingly easy to find the patterns!

Fact 19.2.3.

If \(p^e\) is a perfect prime power, then

\begin{equation*} \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}\text{.} \end{equation*}

Proof.

There isn't much to prove here, once discovered. Both formulas come from the same fundamental observation.

All possible divisors of a prime power must have only that prime as divisors, by the Fundamental Theorem of Arithmetic. So, these divisors are just other (smaller) powers of that prime.
There are exactly \(e+1\) of these divisors, and these divisors are the ones summed up in the \(\sigma_1\) formula.

The fraction formula for \(\sigma_1\) is just the usual geometric summation formula familiar from precalculus, or perhaps calculus.

Subsection 19.2.2 Multiplicativity

It's a bit harder to prove the following. See Definition 18.1.2 to remind yourself of the definition of multiplicative.

Fact 19.2.4.

For any \(i\text{,}\) \(\sigma_i(n)\) is multiplicative. That is,

\begin{equation*} \sigma_i(mn)=\sigma_i(m)\sigma_i(n)\text{ when }\gcd(m,n)=1\text{.} \end{equation*}

This automatically leads to many facts, such as this one.

Theorem 19.2.5.

If we factor \(n > 0\) as

\begin{equation*} n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\text{,} \end{equation*}

then we have formulas

\begin{equation*} \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)\text{.} \end{equation*}

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

Instead, we will prove below a theorem that exemplifies a general principle.

Principle 19.2.6.

In the long run, it is better to prove general results 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\) (recall Fact 9.5.2), but for every arithmetic function.

Subsection 19.2.3 A very powerful lemma

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

Theorem 19.2.7.

If \(g\) is multiplicative and \(f(n)\) is defined as

\begin{equation*} f(n)=\sum_{d\mid n}g(d) \end{equation*}

then \(f\) is also multiplicative.

Proof.

We follow here [E.2.1]. Let \(m\) and \(n\) be coprime; we are interested in \(f(mn)\text{.}\)

Basically, this all boils down to asking what the divisors of \(mn\) look like. Any divisor of \(mn\) must be the product of some divisor \(a\) of \(m\) and some divisor \(b\) of \(n\text{.}\)

The previous observation is just about multiplication and divisibility, not even coprimeness. But that guarantees that \(a\) and \(b\) are coprime as well, given that \(m\) and \(n\) are. So each divisor \(d\mid mn\) gives us a (unique) pair of (coprime) divisors \(a\) and \(b\) of \(m\) and \(n\text{.}\)

Instead of summing over all divisors of \(mn\text{,}\) we can instead sum over each divisor of \(n\) for each divisor of \(m\text{.}\) In symbols,

\begin{equation*} f(mn)=\sum_{a\mid m}\sum_{b\mid n}g(ab)\text{.} \end{equation*}

Now we can use all the facts we have at hand (coprimeness, multiplicativity, etc.) to finish it off.

\begin{equation*} f(mn)=\sum_{a\mid m}\sum_{b\mid n}g(ab)=\sum_{a\mid m}\sum_{b\mid n}g(a)g(b) \end{equation*}

\begin{equation*} =\left(\sum_{a\mid m}g(a)\right)\left(\sum_{b\mid n}g(b)\right)=f(m)f(n)\text{.} \end{equation*}

Corollary 19.2.8.

Since \(g(n)=n^i\) is clearly multiplicative, it is true that

\begin{equation*} \sum_{d\mid n}g(d)=\sum_{d\mid n}d^i=\sigma_i(n) \end{equation*}

is also multiplicative.

The special cases \(i=0\) and \(i=1\) of the corollary confirm that \(\sigma_0=\tau\) and \(\sigma_1=\sigma\) are indeed multiplicative. Since it will be convenient later (see Definition 23.3.1 and following), we give separate names to these two special cases of \(n^i\text{.}\)

Definition 19.2.9.

Let us set the following two arithmetic functions:

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