Science Fair Project Encyclopedia
- f(ab) = f(a) f(b).
An arithmetic function f(n) is said to be completely (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.
Outside number theory, the term multiplicative is usually used for functions with the property f(ab) = f(a) f(b) for all arguments a and b. This article discusses number theoretic multiplicative functions.
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),
- 1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
- 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 if n > 1, 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.
An example of a non-multiplicative function is the arithmetic function r2(n) - the number of representations of n as a sum of squares of two integers, positive, negative, or zero, where in counting the number of ways, reversal of order is allowed. For example:
- 1 = 12 + 02 = (-1)2 + 02 = 02 + 12 = 02 + (-1)2
and therefore r2(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r2(n)/4 is multiplicative.
See arithmetic function for some other examples of non-multiplicative functions.
A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if n is a product of powers of distinct primes, say n = pa qb ..., then f(n) = f(pa) f(qb) ...
This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 24 · 32:
- d(144) = σ0(144) = σ0(24)σ0(32) = (10 + 20 + 40 + 80 + 160)(10 + 30 + 90) = 5 · 3 = 15,
- σ(144) = σ1(144) = σ1(24)σ1(32) = (11 + 21 + 41 + 81 + 161)(11 + 31 + 91) = 31 · 13 = 403,
- σ*(144) = σ*(24)σ*(32) = (11 + 161)(11 + 91) = 17 · 10 = 170.
Similarly, we have:
- φ(144)=φ(24)φ(32) = 8 · 6 = 48
In general, if f(n) is a multiplicative function and a, b are any two positive integers, then
If f and g are two multiplicative functions, one defines a new multiplicative function f * g, the Dirichlet convolution of f and g, by
- (f * g)(n) = ∑d|n f(d)g(n/d)
Relations among the multiplicative functions discussed above include:
- ε = μ * 1 (the Möbius inversion formula)
- φ = μ * Id
- d = 1 * 1
- σ = Id * 1 = φ * d
- σk = Idk * 1
- Id = φ * 1 = σ * μ
- Idk = σk * μ
The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the Dirichlet ring.
- Tom M.Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. ISBN 0-387-90163-9 (See Chapter 2.)
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details