Discrete Mathematics/Arithmetic Functions

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

Euler totient functionEdit

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


Mobius functionEdit

The Mobius function,  


Von Mangoldt functionEdit

The Von Mangoldt function,  




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


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


  1. wikipedia: Euler's totient function