Multiplicative function

related topics
{math, number, function}

In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then

An arithmetic function f(n) is said to be completely multiplicative (or totally multiplicative) if f(1) = 1 and f(ab) = f(a) f(b) holds for all positive integers a and b, even when they are not coprime.

Contents

Examples

Examples of multiplicative functions include many functions of importance in number theory, such as:

  • φ(n): Euler's totient function φ, counting the positive integers coprime to (but not bigger than) n
  • μ(n): the Möbius function, related to the number of prime factors of square-free numbers
  • gcd(n,k): the greatest common divisor of n and k, where k is a fixed integer.
  • d(n): the number of positive divisors of n,
  • σ(n): the sum of all the positive divisors of n,
  • σk(n): the divisor function, which is the sum of the k-th powers of all the positive divisors of n (where k may be any complex number). In special cases we have
    • σ0(n) = d(n) and
    • σ1(n) = σ(n),
  • a(n): the number of non-isomorphic abelian groups of order n.
  • 1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
  • 1C(n) the indicator function of the set C of squares (or cubes, or fourth powers, etc.)
  • Id(n): identity function, defined by Id(n) = n (completely multiplicative)
  • Idk(n): the power functions, defined by Idk(n) = nk for any natural (or even complex) number k (completely multiplicative). As special cases we have
    • Id0(n) = 1(n) and
    • Id1(n) = Id(n),
  • ε(n): the function defined by ε(n) = 1 if n = 1 and = 0 otherwise, sometimes called multiplication unit for Dirichlet convolution or simply the unit function; sometimes written as u(n), not to be confused with μ(n) (completely multiplicative).
  • (n/p), the Legendre symbol, where p is a fixed prime number (completely multiplicative).
  • λ(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
  • γ(n), defined by γ(n)=(-1)ω(n), where the additive function ω(n) is the number of distinct primes dividing n.
  • All Dirichlet characters are completely multiplicative functions.

Full article ▸

related documents
Paracompact space
Prim's algorithm
Riemann mapping theorem
Recursive descent parser
Augmented Backus–Naur Form
Open set
Outer product
Depth-first search
Existential quantification
Jules Richard
Gram–Schmidt process
Base (topology)
Poisson process
Octal
Rank (linear algebra)
Pigeonhole principle
Riesz representation theorem
Trie
ML (programming language)
Boolean ring
Merkle-Hellman
Legendre polynomials
Closure (topology)
2 (number)
Procedural programming
Delegation pattern
Hyperbolic function
Arity
Preorder
Presburger arithmetic