Subsection 24.1.1 Products
Let
\(p\mid n\) as an indexing tool denote the set of primes which divide
\(n=\prod_{p\text{ prime }}p^e\) (recall
Example 6.3.4). Then we have the following
product representation of two familiar arithmetic functions. (Recall
Theorem 19.2.5 and
Fact 18.1.1.)
\begin{equation*}
\sigma(n)=\prod_{p\mid n}\left(\frac{p^{e+1}-1}{p-1}\right)=\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right)
\end{equation*}
\begin{equation*}
\phi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)
\end{equation*}
Both of these functions therefore may be thought of as (finite) products.
As a related example, we explicitly wrote out the product for the abundancy index in
Section 19.3.
\begin{equation*}
\frac{\sigma(n)}{n}=\frac{\prod_{p\mid n} \left(\frac{p^{e+1}-1}{p-1}\right)}{\prod_{p\mid n} p^{e}} = \prod_{p\mid n}\frac{p-\left(1/p^{e}\right)}{p-1}
\end{equation*}
Alternately, to avoid fractions:
\begin{equation*}
\frac{\sigma(n)}{n}=\frac{\prod_{p\mid n}\left(1+p+p^2+\cdots+p^e\right)}{\prod_{p\mid n}p^e}=\prod_{p\mid n}\left(1+p^{-1}+p^{-2}+\cdots + p^{-e}\right)
\end{equation*}
Note that \(\frac{\phi(n)}{n} = \prod_{p\mid n} \left(1-\frac{1}{p}\right)\text{.}\)
Subsection 24.1.2 Products that are sums
On the other hand, these products over primes are also sums over divisors; this is true either by definition or by theorem, depending on how you look at it.
It’s clear with
\(\sigma\) that this is the case, since we defined (in
Definition 19.1.1)
\begin{equation*}
\sigma(n)=\sum_{d\mid n}d
\end{equation*}
We can even cleverly add up the divisors in the opposite order to get the slightly more felicitous
\begin{equation*}
\sigma(n)=\sum_{d\mid n}\frac{n}{d}=n\sum_{d\mid n}\frac{1}{d}\text{.}
\end{equation*}
This led us directly to writing
\(\frac{\sigma(n)}{n}=\sum_{d\mid n}\frac{1}{d}\) in
Fact 19.4.9; now we can also write it as
\(\sum_{d\mid n}\frac{u(d)}{d}\text{.}\)
With
\(\phi\) we have something to prove to make this connection, but not much. In
Fact 23.3.2 we saw that
\(\phi\star u=N\Rightarrow \phi=N\star \mu\text{.}\) Equivalently, we have Möbius-inverted
Fact 9.5.4 to obtain, from
\(\sum_{d\mid n}\phi(d)=n\text{,}\) the formula
\begin{equation*}
\sum_{d\mid n}d\mu\left(\frac{n}{d}\right)=\phi(n)
\end{equation*}
By adding the divisors in the opposite order (alternately, by noting \(\star\) is commutative) we can write
\begin{equation*}
\phi(n)=\mu\star N=\sum_{d\mid n}\mu(d)\left(\frac{n}{d}\right)=n\sum_{d\mid n}\frac{\mu(d)}{d}\text{,}
\end{equation*}
which allows us to also write the fraction as
\begin{equation*}
\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}\text{.}
\end{equation*}
Now, in some sense we already knew all this. Great, some arithmetic functions can be represented either as a sum over divisors or as a product over primes, depending on what you need from them. So what?
The genius of Euler was to directly connect these ideas.
Fact 24.1.1.
We can equate sums over divisors and products over primes to obtain special formulas. Given \(n=\prod_{p\text{ prime }}p^e\text{,}\) we have
\begin{equation*}
\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}=\prod_{p\mid n}\left(1-\frac{1}{p}\right)
\end{equation*}
\begin{equation*}
\frac{\sigma(n)}{n}=\prod_{p\mid n}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots+ \frac{1}{p^{e}}\right)=\sum_{d\mid n}\frac{1}{d}\text{.}
\end{equation*}
Well, this was almost the genius; his real genius was to take these ideas to the limit!
One can’t really take these expressions to infinity as they stand – one would get massive divergence. So what can we do? To analyze this, we will define new, related functions which preserve the summation, but allow for convergence.
