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:

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$:

The mobius function will allow us to perform mobius inversion :

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

§ associativity, commutativity of $\star$

To prove associativity, it's better to write the formula as:

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:

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$.

§ $\mu$ as the inverse of the $one$ function

§ Mobius inversion

Now that we know that $\mu = \texttt{const 1}^{-1}$, we can use this fact to perform mobius inversion :

We have $f$ written in terms of $g$. We can now write $g$ in terms of $f$:

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

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:

In general, the same argument allows us to prove that:

§ Using mobius inversion on the euler totient function

§ Other arithmetical functions and their relations