In number theory, an arithmetic function f(n) is called a multiplicative function if it possesses the property that f(ab)=f(a)f(b) for any positive integers a and b which are coprime (gcd(a,b)=1). Note that since gcd(n,1)=1 for any positive integer n, we see that for any multiplicative function, f(1)=1.
If the property f(ab)=f(a)f(b) holds for all positive integers a and b, coprime or not, then the function is said to be completely multiplicative.
One example of a multiplicative function is Euler’s totient function φ(n) (some others may be found here).
Now, consider the prime factorization of n:
. Plugging this into a multiplicative function, we see:
.
Thus, a multiplicative function is determined completely by its values for the powers of the prime numbers. This simplifies the computation of multiplicative functions. For example, consider φ(n). For a power of a prime pk, k>0, the only positive integers less than or equal to this number which aren’t coprime with it are multiples of p: p, 2p, 3p, … , (pk-1)p=pk; this is pk-1 numbers, so the totient is
. This allows us to compute the totient of any number from it’s prime factorization, e.g.:
φ(720)=φ(24325)
=φ(24)φ(32)φ(5)
=24-1(2-1)·32-1(3-1)·51-1(5-1)
=8·6·4=192
Let f(n) and g(n) be multiplicative functions, and let h(n)= f(n)g(n) be their product. Then for any coprime positive integers a and b,
,
so the product of two multiplicative functions is multiplicative.
Tags: Arithmetic Function, Math, Monday Math, Multiplicative Function, Number Theory, Prime Numbers, Totient
August 24, 2009 at 12:07 am |
[...] Math 86 By twistedone151 A notable multiplicative function is the Möbius function μ(n) defined as follows: μ(n)=1 when n is a square-free integer with [...]
October 5, 2009 at 1:12 am |
[...] the Dirichlet convolution is also associative: f*(g*h)=(f*g)*h. Now, suppose that f and g are both multiplicative functions. Then let us consider (f*g)(mn), where m and n are coprime: . Let d1 be any divisor of m, and d2 be [...]
November 23, 2009 at 12:24 am |
[...] totient function. Our result about ab with coprime a and b thus follows from φ(n) being a multiplicative function. Since for prime p, we see that , again confirming that if n gives us a constructible polygon, n [...]
November 25, 2010 at 10:42 am |
[...] consider Euler’s totient function φ(n). It is a multiplicative function, and I showed here that for prime p and positive k, so the Dirichlet series generating function will have prime [...]