Discrete Mathematics/Arithmetic Functions

An arithmetic function is a function from the set of positive integers to the set of complex numbers. Examples of important arithmetic functions include:

Euler totient function

The Euler totient function, $\phi (n)$ defined to be the number of positive integers less than and relatively prime to n

$\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),$

Mobius function

The Mobius function, $\mu (n)={\begin{cases}1,&{\mbox{if }}n\;{\mbox{is square free with an even number of prime factors}}\\-1,&{\mbox{if }}n\;{\mbox{is square free with an odd number of prime factors}}\\0&{\mbox{otherwise}}\end{cases}}$

$e(n)={\begin{cases}1,&{\mbox{if }}n=1\\0,&{\mbox{otherwise}}\end{cases}}$

Von Mangoldt function

The Von Mangoldt function, $\Lambda (n)={\begin{cases}\ln p,&{\mbox{if }}n=p^{k}{\mbox{ for some prime}}p{\mbox{and}}k\geq 1\\0,&{\mbox{otherwise}}\end{cases}}$

$\sigma _{k}(n)=\sum _{d|n}d^{k}$

and

$\theta _{k}(n)=n^{k}$

Many of these functions are multiplicative that is they satisfy a(m)a(n)=a(mn) when m and n are relatively prime. A function that satisfies a(m)a(n)=a(mn) even when m & n are not relatively prime is called completely multiplicative. To define a multiplicative function, a(n), it suffices to only give its values when n is the power of a prime; For a completely multiplicative function, giving its values when n is prime uniquely defines the function.

Given 2 arithmetic functions their Dirichlet convolution is defined by

$(a*b)(n)=\sum _{d|n}a(d)b({\frac {n}{d}})$

where the sum is taken over the divisors, d, of n. It is easy to show that

$(a*e)(n)=a(n)$,

that is the function e(n) is the identity under Dirichlet convolution. Another basic fact is that Dirichlet convolution is commutative and associative.

It is also straightfoward to show that multiplicative functions form a group under Dirichlet convolution, or in other words, the following properties hold in addition to the fact that e(n) is the identity, and its associativity:

• for any multiplicative function a there is a multiplicative function b such that (a * b) = e

and

• the Dirichlet convolution of 2 multiplicative functions is also multiplicative.

The most important fact about the Von Mangoldt function is that

$\sum _{d|n}\Lambda (n)=\ln n$.

The Mobius function's significance comes from the fact that

$\sum _{d|n}\mu (n)=e(n)$,

and thus if $f(n)=\sum _{d|n}g(d)$ then $g(n)=\sum _{d|n}f(d)\mu ({\frac {n}{d}})$.