Discrete Mathematics/Arithmetic Functions

From Wikibooks, open books for an open world
Jump to: navigation, search

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,


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 .