Long (but more easily generalised) proof:
DefinitionAn arithmetic function is a complex-valued function defined on the natural numbers, that is, a function
.
Example(1) The identity function
defined by
 = \left\lfloor \frac{1}{n} \right\rfloor = \begin{cases}<br />1 & \text{if $n = 1$,} \\<br />0 & \text{if $n > 1$.}<br />\end{cases}\])
(2) The unity function
defined by
 = 1 \quad \text{for all $n \in \mathbb{N}$.}<br />\])
(3) The Mobius function}
defined by
 = \begin{cases}<br />1 & \text{if $n = 1$,} \\<br />(-1)^k & \text{if $n = p_1^{a_1} \cdots p_k^{a_k}$ with $a_1 = \ldots = a_k = 1$,} \\<br />0 & \text{otherwise.}<br />\end{cases}\])
DefinitionAn arithmetic function is multiplicative if, for
,
 = f(m)f(n))
whenever
 = 1)
(that is, whenever
and
are coprime).
LemmaA multiplicative functions is completely determined by its values on prime powers.
ProofThis is a simple application of the fundamental theorem of arithmetic.
DefinitionThe Dirichlet convolution of two arithmetic functions
is the function
defined by
 = \sum_{d \mid n}{f(d) g\left(\frac{n}{d}\right)}.)
PropositionIf
and
are multiplicative, then their Dirichlet convolution
is also multiplicative.
ProofIf
, then every divisor
of
can be written uniquely in the form
, where
and
, and so
 & = \sum_{d \mid mn}{f(d) g\left(\frac{mn}{d}\right)} \\<br />& = \sum_{\substack{a \mid m \\ b \mid n}}{f(ab) g\left(\frac{mn}{ab}\right)} \\<br />& = \sum_{a \mid m}{f(a)g\left(\frac{m}{a}\right)} \sum_{b \mid n}{f(b) g\left(\frac{n}{b}\right)} \\<br />& = f*g(m) f*g(n).<br />\end{align*})
Combining everything, we can prove the following theorem.
TheoremWe have the identity
} = \begin{cases} 1 & \text{if $n = 1$,} \\ 0 & \text{if $n > 1$.} \end{cases})
ProofWe must show that
. As
is multiplicative, being the Dirichlet convolution of two multiplicative functions, it suffices to show this merely for prime powers. So for a prime power
, we have
 = \sum_{d \mid p^a}{\mu(d) 1_{\mathbb{N}}\left(\frac{n}{d}\right)} = \sum^{a}_{i=0}{\mu(p^i)} = \begin{cases}<br />1 & \text{if $a = 0$,} \\<br />0 & \text{otherwise,} \\<br />\end{cases}<br />\])
as
 = 1)
,
 = -1)
, and
 = 0)
for
.
Obviously this proof can be trimmed down a fair bit, but it's very useful for showing other identities among arithmetic functions.
Home
Help
Search
Login
