Monday Math 85

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.

Advertisements

Tags: , , , , , ,

4 Responses to “Monday Math 85”

  1. Monday Math 86 « Twisted One 151’s Weblog Says:

    […] 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 […]

  2. Monday Math 91 « Twisted One 151’s Weblog Says:

    […] 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 […]

  3. Monday Math 98 « Twisted One 151’s Weblog Says:

    […] 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 […]

  4. Monday Math 88 « Twisted One 151's Weblog Says:

    […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: