Multiplicative function - AbsoluteAstronomy.com

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, a multiplicative function is an arithmetic function

Arithmetic function

In number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...

f(n) of the positive integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

n with the property that f(1) = 1 and whenever
a and b are coprime

Coprime

In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

, then

f(ab) = f(a) f(b).

An arithmetic function f(n) is said to be completely multiplicative
Completely multiplicative function
In number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. Especially in number theory, a weaker condition is also important, respecting only products of coprime numbers, and such...

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

Examples

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

(n): Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...

, counting the positive integers coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

to (but not bigger than) n
(n): the Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...

, related to the number of prime factors of square-free
Square-free integer
In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...

numbers
gcd(n,k): the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

of n and k, where k is a fixed integer.
d(n): the number of positive divisor
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

s of n,
(n): the sum of all the positive divisors of n,
_k(n): the divisor function
Divisor function
In mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships...

, which is the sum of the k-th powers of all the positive divisors of n (where k may be any complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

). In special cases we have
- ₀(n) = d(n) and
- ₁(n) = (n),
: the number of non-isomorphic abelian groups of order n.
1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
the indicator function of the set of squares (or cubes, or fourth powers, etc.)
Id(n): identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

, defined by Id(n) = n (completely multiplicative)
Id_k(n): the power functions, defined by Id_k(n) = n^k for any natural
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

(or even complex) number k (completely multiplicative). As special cases we have
- Id₀(n) = 1(n) and
- Id₁(n) = Id(n),
(n): the function defined by (n) = 1 if n = 1 and 0 otherwise, sometimes called multiplication unit for Dirichlet convolution
Dirichlet convolution
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Johann Peter Gustav Lejeune Dirichlet, a German mathematician.-Definition:...

or simply the unit function; sometimes written as u(n), not to be confused with (n) (completely multiplicative).
(n/p), the Legendre symbol
Legendre symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....

, where p is a fixed prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

(completely multiplicative).
(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
(n), defined by (n)=(-1)⁽ⁿ⁾, where the additive function
Additive function
In mathematics the term additive function has two different definitions, depending on the specific field of application.In algebra an additive function is a function that preserves the addition operation:for any two elements x and y in the domain. For example, any linear map is additive...

(n) is the number of distinct primes dividing n.
All Dirichlet character
Dirichlet character
In number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of \mathbb Z / k \mathbb Z...

s are completely multiplicative functions.

An example of a non-multiplicative function is the arithmetic function r₂(n) - the number of representations of n as a sum of squares of two integers, positive, negative, or zero

0 (number)

0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...

, where in counting the number of ways, reversal of order is allowed. For example:

1 = 1² + 0² = (-1)² + 0² = 0² + 1² = 0² + (-1)²

and therefore r₂(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r₂(n)/4 is multiplicative.

In the On-Line Encyclopedia of Integer Sequences

On-Line Encyclopedia of Integer Sequences

The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...

, sequences of values of a multiplicative function have the keyword "mult".

See arithmetic function

Arithmetic function

for some other examples of non-multiplicative functions.

Properties

A multiplicative function is completely determined by its values at the powers of prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

s, a consequence of the fundamental theorem of arithmetic

Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...

. Thus, if n is a product of powers of distinct primes, say n = p^a q^b ..., then
f(n) = f(p^a) f(q^b) ...

This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 2⁴ · 3²:

d(144) =

₀(144) =

₀(2⁴)

₀(3²) = (1⁰ + 2⁰ + 4⁰ + 8⁰ + 16⁰)(1⁰ + 3⁰ + 9⁰) = 5 · 3 = 15,

(144) =

₁(144) =

₁(2⁴)

₁(3²) = (1¹ + 2¹ + 4¹ + 8¹ + 16¹)(1¹ + 3¹ + 9¹) = 31 · 13 = 403,

^*(144) =

^*(2⁴)

^*(3²) = (1¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170.

Similarly, we have:

(144)=

(2⁴)

(3²) = 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

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

(a,b)) · f(lcm

Least common multiple

In arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...

(a,b)).

Every completely multiplicative function is a homomorphism

Homomorphism

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...

of monoid

Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...

s and is completely determined by its restriction to the prime numbers.

Convolution

If f and g are two multiplicative functions, one defines a new multiplicative function f * g, the Dirichlet convolution
Dirichlet convolution
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Johann Peter Gustav Lejeune Dirichlet, a German mathematician.-Definition:...

of f and g, by

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

Abelian group

In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

; the identity element

Identity element

In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

.

Relations among the multiplicative functions discussed above include:

* 1 = (the Möbius inversion formula
Möbius inversion formula
In mathematics, the classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. Other Möbius inversion formulas are obtained when different local finite partially ordered sets replace the classic case of the natural numbers ordered by...

)
( * Id_k) * Id_k = (generalized Möbius inversion)
* 1 = Id
d = 1 * 1
= Id * 1 = * d
_k = Id_k * 1
Id = * 1 = *
Id_k = _k *