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

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

The Mobius function,

The Von Mangoldt function,

and

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

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

,

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

.

The Mobius function's significance comes from the fact that

,

and thus if then .