|
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 Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ...
In number theory, an arithmetic function (or number-theoretic function) f(n) is a function defined for all positive integers and having values in the complex numbers. ...
The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...
Coprime - Wikipedia /**/ @import /skins-1. ...
- 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 requires either f(1) = 1, or f(a) = 0 for all a except a = 1. This article discusses number theoretic multiplicative functions.
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),
- 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: In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...
Coprime - Wikipedia /**/ @import /skins-1. ...
The classical Möbius function is an important multiplicative function in number theory and combinatorics. ...
In mathematics, a square-free integer is one divisible by no perfect square, except 1. ...
In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...
In mathematics the divisor function σa(n) is defined as the sum of the ath powers of the divisors of n, or The notations d(n) and (the tau function) are also used to denote σ0(n), or the number of divisors of n. ...
In mathematics, the complex numbers are an extension of the real numbers by the inclusion of the imaginary unit i, satisfying . ...
An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ...
Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...
The Legendre symbol is used by mathematicians in the area of number theory, particularly in the fields of factorization and quadratic residues. ...
In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ...
The Liouville function, denoted by λ(n) and named after Joseph Liouville, is an important function in number theory. ...
In number theory, an additive function is an arithmetic function f(n) of the positive integer n such that whenever a and b are coprime we have: f(ab) = f(a) + f(b). ...
In number theory, a Dirichlet character is a function χ from the positive integers to the complex numbers which has the following properties: There exists a positive integer k such that χ(n) = χ(n + k) for all n. ...
A negative number is a number that is less than zero, such as −3. ...
A negative number is a number that is less than zero, such as −3. ...
0 (zero) or nought is both a number and a numeral. ...
- 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. In number theory, an arithmetic function (or number-theoretic function) f(n) is a function defined for all positive integers and having values in the complex numbers. ...
Properties 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) ... In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ...
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 - f(a) · f(b) = f(gcd(a,b)) · f(lcm(a,b)).
Every completely multiplicative function is a homomorphism of monoids and is completely determined by its restriction to the prime numbers. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...
In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...
In abstract algebra, a homomorphism is a map from one algebraic structure to another of the same type that preserves all the relevant structure. ...
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...
Convolution If f and g are two multiplicative functions, one defines a new multiplicative function f * g, the Dirichlet convolution of f and g, by In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is of importance in number theory. ...
- (f * g)(n) = ∑d |n f(d)g(n/d)
where the sum extends over all positive divisors d of n. With this operation, the set of all multiplicative functions turns into an abelian group; the identity element is ε. In mathematics, an abelian group, also called a commutative group, is a group (G, *) such that a * b = b * a for all a and b in G. Abelian groups are named after Niels Henrik Abel. ...
In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...
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. The classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. ...
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is of importance in number theory. ...
See also In mathematics, an Euler product is an infinite product expansion, indexed by prime numbers p, of a Dirichlet series. ...
In mathematics, the Bell series is a formal power series used to study properties of multiplicative arithmetical functions. ...
A Lambert series, named after Johann Heinrich Lambert, is a series taking the form It can be resummed by expanding the denominator: where the coefficients of the new series are given by the Dirichlet convolution of with the constant function Since this last sum is a typical number-theortic sum...
References - Tom M.Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. ISBN 0-387-90163-9 (See Chapter 2.)
|
Feeds |
Contact