## § Dirichlet inversion

We call all functions $f: \mathbb Z \rightarrow \mathbb R$ as arithmetic functions, since they operate on the integers. We introduce an operator $f \star g: \mathbb Z \rightarrow \mathbb R$. It is defined by:
• $(f \star g)(n) \equiv \sum_{d \vert n} f(d) g(n/d)$
We will show that the set of arithmetic functions forms a group under the operator $\star$, with identity:
$id_\star(n) \equiv \lfloor 1/n \rfloor = \begin{cases} 1 & n = 1 \\ 0 & \text{otherwise} \end{cases}$
The reason all of this is interesting is that the inverse of the constant function $1(n) \equiv 1$ is going to be this function called as the mobius function $\mu$:
$\mu(n=p_1^{\alpha_1} p_2^{\alpha_2} \dots p_r^{\alpha_r}) \equiv \begin{cases} 0 & \text{if any \alpha_i > 1} \\ (-1)^{\alpha_1 + \alpha_2 + \dots + \alpha_r} & \text{if all \alpha_i \in \{ 0, 1 \}} \end{cases}$
The mobius function will allow us to perform mobius inversion:
\begin{aligned} f(n) &\equiv \sum_{d \vert n} g(d) = \sum_{d \vert n} g(d) 1(n/d) = g \star 1 \\ f \star 1^{-1} &= g \star 1 \star 1^{-1} \\ f \star \mu &= g \end{aligned}
That is, we originally had $f$ defined in terms of $g$. We can recover an expression for $g$ in terms of $f$.

#### § The algebra of multiplicative functions

We claim that the set of functions $\{ \mathbb Z \rightarrow \mathbb C \}$ is a commutative group, with the group operation $\star$ such that:
• $(f \star g)(n) \equiv \sum_{d \vert n} f(d) g(n/d)$.
with the identity element being $id_\star(n) \equiv \lfloor 1 / n \rfloor$. The idea is that if $(n = 1)$, then $\lfloor 1/1 \rfloor = 1$, and for any other number $n > 0$, $1/n < 1$, hence $\lfloor 1/n \rfloor = 0$.

#### § verification of $istar$ being the identity

\begin{aligned} &(f \star id_\star)(n) \equiv \sum_{d \vert n} f(d) id_\star(n/d) \\ &= f(n) id_\star(1) + \sum_{d \vert n, d > 1} f(n) id_\star(d) \\ &= f(n) \cdot 1 + \sum_{d \vert n, d > 1} f(n) \cdot 0 \\ &= f(n) \\ \end{aligned}

#### § associativity, commutativity of $\star$

To prove associativity, it's better to write the formula as:
$(f \star g)(n) \equiv \sum_{d \vert n} f(n) g(n/d) = \sum_{xy = n} f(x) g(y)$
From this rewrite, it's clear that $(f \star g \star h)(n)$ will unambiguously sum over tripes $(x, y, z)$ such that $xyz = n$. I leave the working-this-out to you. This should also make the commutativity immediate. Summing over pairs of the form $f(x) g(y) : xy = n$ is the same as summing over $f(y) g(x) : yx = n$.

#### § Existence of inverse

We can show that an inverse exists by showing that a formula for it exists; The idea is to construct one by induction. Clearly, for a given function $f$, we need the inverse $f^{-1}$ to be such that $(f \star f^{-1})(n) = id_\star$. Hence:
\begin{aligned} &(f \star f^{-1})(1) = id_\star(1) = 1 \\ &f(1) f^{-1}(1) = 1 \\ & f^{-1}(1) \equiv 1 / f(1)\\ \end{aligned}
Great, we have a base case; We can now compute $f^{-1}(n)$ inductively, assuming we know the value of $f^{-1}(d)$ for all $d \vert n$.
\begin{aligned} &(f \star f^{-1})(n) = id_\star(1) = 0 \\ &\sum_{d \vert n} f(d) f^{-1}(n/d) = 0 \\ &f(1) f^{-1}(n) + \sum_{d \vert n, d < n} f(d) f^{-1}(n/d) = 0 \\ &f^{-1}(n) = -\frac{\sum_{d \vert n, d < n} f(d) f^{-1}(n/d)}{f(1)} \end{aligned}

#### § Mobius inversion

Now that we know that $\mu = \texttt{const 1}^{-1}$, we can use this fact to perform mobius inversion:
$f(n) \equiv \sum_{d \vert n} g(n/d) = \texttt{const 1} \star g$
We have $f$ written in terms of $g$. We can now write $g$ in terms of $f$:
\begin{aligned} &f(n) = \texttt{const 1} \star g \\ &f \star \texttt{const 1}^{-1} = g \\ &g = f \star \mu \\ &g = \sum_{d \vert n} f(d) \mu(n/d) \end{aligned}

#### § $n = \sum_{d \vert n} \phi(d)$

$\begin{array}{|c|c|c|c|} d & \{ 1 \leq x \leq 12 : (x, 12) = d \} & \{ 1 \leq x \leq 12: (x/d, 12/d) = 1\} & \text{size of set} \\ 1 & \{ 1, 5, 7, 11 \} & (x, 12) = 1 & 4 \\ 2 & \{2, 10 \} & (x/2, 6) = 1& 2 \\ 3 & \{3, 9 \} & (x/3, 4) = 1 & 2 \\ 4 & \{4, 8 \} & (x/4, 3) = 1 & 2 \\ 6 & \{ 6 \} & (x/6, 2) = 1 & 1 \\ 12 & \{ 12 \} (x/12, 1) = 1 & 1 \end{array}$
Notice that the sizes of sets that we are calculating, for example, $|\{ 1 \leq x \leq 12 : (x/2, 6) = 1 \}| = \phi(6)$. Summing over all of what we have, we've counted the numbers in $[1, 2, \dots, 12]$ in two ways --- one directly, and the other by partitioning into equivalence classes:
$12 = \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(12) = \sum_{d \vert 12} \phi(12/d)$
In general, the same argument allows us to prove that:
$n = \sum_{d \vert n} n/d$