I'm going to describe a formula for computing which uses the prime factorization of n. This will require some preliminaries on divisor sums.
Definition. An arithmetic function is a function defined on the positive integers which takes values in the real or complex numbers.
Examples. (a) Define by . Then f is an arithmetic function.
(b) The Euler phi function is an arithmetic function.
(c) Define by
For example, , since there are 6 positive divisors of 12 --- 1, 2, 3, 4, 6, and 12. is an arithmetic function.
(d) Define by
Since 1, 2, 3, 6, 9, and 18 are the positive divisors of 18,
is an arithmetic function.
Definition. The Möbius function is the arithmetic function defined by , and for ,
Thus, if n is divisible by a square.
Example. , since . Likewise, , since . But and .
Definition. If f is an arithmetic function, the divisor sum of f is
To save writing, I'll make the convention that when I write " ", I mean to sum over all the {\it positive} divisors of a positive integer n. Thus, the divisor sum of f evaluated at a positive integer n takes the positive divisors of n, plugs them into f, and adds up the results.
Notice that the divisor sum is a function which takes an arithmetic function as input and produces an arithmetic function as output.
Example. Suppose is defined by . Then
For example,
Lemma.
Proof. The formula for is obvious.
Suppose . Let
be the factorization of n into distinct primes. What are the nonzero terms in the sum ? They will come from d's which are products of single powers of , ... , and also .
For example, and would give rise to nonzero terms in the sum, but .
So
Example. Suppose . The divisor sum is
Definition. If f and g are arithmetic functions, their Dirichlet product is
Example. If f and g are arithmetic functions,
I'll need two helper functions in what follows. Define
Proposition. Let f, g, and h be arithmetic functions.
(a) .
(b) .
(c) .
(d) .
(e) .
Proof. For (a), note that divisors of n come in pairs , and that if is a divisor pair, so is . This means that the same terms occur in both
Hence, they're equal.
Associativity is a little tedious, so I'll just note that and are equal to
Here the sum runs over all triples of positive numbers d, e, f such that . You can fill in the details.
For (c), note that
( is 0 except when , i.e. when .)
For (d),
For (e), start with :
Now suppose . Then
Therefore, the formula holds for all n.
The next result is very powerful, but the proof will look easy with all the machinery I've collected.
Theorem. ( Möbius Inversion Formula) If f is an arithmetic function, then .
Proof.
Next, I'll compute the divisor sum of the Euler phi function.
Lemma.
Proof. Let n be a positive integer. Construct the fractions
Reduce them all to lowest terms. Consider a typical lowest-term fraction . Here (because it came from a fraction whose denominator was n, (because the original fraction was less than 1), and (because it's in lowest terms).
Notice that (going the other way) if is a fraction with positive top and bottom which satisfies , , and , then it is one of the lowest-terms fractions. For for some k, and then --- and the last fraction is one of the original fractions.
How many of the lowest-terms fractions have "d" on the bottom? Since the "a" on top is a positive number relatively prime to d, there are such fractions. Summing over all d's which divide n gives . But since every lowest-terms fraction has some such "d" on the bottom, this sum accounts for all the fractions --- and there are n of them. Therefore, .
Example. Suppose . Then
Lemma. Let .
Proof. By Möbius inversion and the previous result,
Example. Take , so .
Theorem. Let .
(By convention, the empty product --- the product with no terms --- equals 1.)
Proof. If , the result is immediate by convention.
If , let , ..., be the distinct prime factors of n. Then
Each term is , where d is 1 (the first term) or a product of distinct primes. The in front of each term alternates signs according to the number of p's --- which is exactly what the Möbius function does. So the expression above is
(I can run the sum over all divisors, because if d has a repeated prime factor.) Now simply multiply by n:
Example. , so
Likewise, , so
More generally, if p is prime and , then
For
Definition. An arithmetic function f is multiplicative if implies
Lemma. is multiplicative --- that is, if , then
Proof. Suppose . Now
So
Since , the two products have no primes in common. Moreover, the primes that appear in either of the products are exactly the prime factors of . So
Hence,
Example. If , then is even. In fact, if n has k odd prime factors, then .
To see this, observe first that
This is even if .
So suppose that n has k odd prime factors. Then
The denominator of the fraction is the product of primes dividing n, so the fraction is actually an integer. The second term has at least one even factor for each odd prime dividing n, because if p is an odd prime then is even. Hence, the second term --- and therefore --- is divisible by .
For example, consider . There are 3 odd prime factors, so should be divisible by 8. And in fact, .
Copyright 2008 by Bruce Ikenaga