Multiplicative function

From Academic Kids

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

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.

Contents

Examples

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

  • <math>\phi<math>(n): Euler's Totient function <math>\phi<math>, counting the positive integers coprime to (but not bigger than) n
  • <math>\mu<math>(n): the Mbius 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,
  • <math>\sigma<math>(n): the sum of all the positive divisors of n,
  • <math>\sigma<math>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
    • <math>\sigma<math>0(n) = d(n) and
    • <math>\sigma<math>1(n) = <math>\sigma<math>(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),
  • <math>\epsilon<math>(n): the function defined by <math>\epsilon<math>(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 <math>\mu<math>(n) (completely multiplicative).
  • (n/p), the Legendre symbol, where p is a fixed prime number (completely multiplicative).
  • <math>\lambda<math>(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
  • <math>\gamma<math>(n), defined by <math>\gamma<math>(n)=(-1)<math>\omega<math>(n), where the additive function <math>\omega<math>(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.

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

This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 24 32:

d(144) = <math>\sigma<math>0(144) = <math>\sigma<math>0(24)<math>\sigma<math>0(32) = (10 + 20 + 40 + 80 + 160)(10 + 30 + 90) = 5 3 = 15,
<math>\sigma<math>(144) = <math>\sigma<math>1(144) = <math>\sigma<math>1(24)<math>\sigma<math>1(32) = (11 + 21 + 41 + 81 + 161)(11 + 31 + 91) = 31 13 = 403,
<math>\sigma<math>*(144) = <math>\sigma<math>*(24)<math>\sigma<math>*(32) = (11 + 161)(11 + 91) = 17 10 = 170.

Similarly, we have:

<math>\phi<math>(144)=<math>\phi<math>(24)<math>\phi<math>(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.

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

(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 <math>\epsilon<math>.

Relations among the multiplicative functions discussed above include:

  • <math>\epsilon<math> = <math>\mu<math> * 1 (the Mbius inversion formula)
  • <math>\phi<math> = <math>\mu<math> * Id
  • d = 1 * 1
  • <math>\sigma<math> = Id * 1 = <math>\phi<math> * d
  • <math>\sigma<math>k = Idk * 1
  • Id = <math>\phi<math> * 1 = <math>\sigma<math> * <math>\mu<math>
  • Idk = <math>\sigma<math>k * <math>\mu<math>

The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the Dirichlet ring.

See also

References

es:Funcin multiplicativa fr:Fonction multiplicative it:Funzione moltiplicativa ko:곱셈적 함수 sv:Multiplikativ funktion zh:積性函數

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools