In this section, I'll derive some formulas for . I'll also show that has an important property called multiplicativity. To put this in the proper context, I'll discuss arithmetic functions, Dirichlet products, and the Möbius inversion formula.
In case you prefer a more direct approach to the formulas and properties of , I give an alternative proof of the multiplicativity of in the appendix to this section.
Definition. An arithmetic function is a function defined on the positive integers which takes values in the real or complex numbers.
For instance, define by . Then f is an arithmetic function.
Many functions which are important in number theory are arithmetic functions. For example:
(a) The Euler phi function is an arithmetic function.
(b) Define the number of divisors function by
For example, , since there are 6 positive divisors of 12 --- 1, 2, 3, 4, 6, and 12. is an arithmetic function.
(c) Define the sum of divisors function by
Since 1, 2, 3, 6, 9, and 18 are the positive divisors of 18,
is an arithmetic function.
In order to find ways of computing , , and , we can use the following approach: First, compute the function for p, where p is prime.
Next, compute the function for , where p is prime and .
Finally, for a general number n, factor n into a product of powers of primes and use the result for .
In order to make the jump from prime powers to an arbitrary integer, we'll show that the functions in question are multiplicative. While it's possible to do this directly for each function, we can also prove results which will allow us to use the same approach for , , and . These results are important for other applications.
Definition. The Möbius function is the arithmetic function defined by , and for ,
Thus, if n is divisible by a square.
For 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 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. A similar convention will hold for products.
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 . Compute .
is the sum of the squares of the divisors of n:
Proof. The formula for is obvious.
Suppose . Factor n into a product of powers of 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 .
Example. Verify the previous lemma for .
The divisor sum is
Definition. If f and g are arithmetic functions, their Dirichlet product is
For example for arithmetic functions f and g, the Dirichlet product evaluated at 12 is
Definition. Define arithmetic functions
Proposition. Let f, g, and h be arithmetic functions.
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 (e), start with :
Now suppose . Then by (d), , so
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
Next, I'll compute the divisor sum of the Euler phi function.
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, .
For example, suppose . Then
Lemma. Let .
Proof. By Möbius inversion and the previous result,
For instance, suppose , so . Then
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:
The formula in the theorem is useful for hand-computations of . For example, , so
Likewise, , so
Definition. An arithmetic function f is multiplicative if implies
Proposition. is multiplicative --- that is, if , then
Proof. Suppose . Now
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
Corollary. Let , and consider its prime factorization:
(Here the p's are distinct primes, and the r's are positive integers.) Then
Proof. Note that if , then . That is, the prime powers in the prime factorization of n are relatively prime. Recall that if p is prime, then
These observations combined with the fact that is multiplicative give
The second formula follows from the first by factoring out common factors from each term.
Note that in the second formula a prime power gives a "real" term only if . If is the highest power of p which divides n, then the corresponding term in the second formula for is just --- and so, if you don't know the value of r in , the only term you can assume will appear in is .
While the formula in the earlier theorem provided a way of computing , the formula in the corollary is often useful in proving results about .
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. Each odd prime power factor in the prime factorization of n gives a term in the product for in the corollary, and each term is even (since it's a difference of odd numbers).
Hence, is divisible by .
For example, consider . There are 3 odd prime factors, so should be divisible by 8. And in fact, .
Example. Find all positive integers n such that .
I'll do this in steps. First, I'll show that no prime can divide n.
At that point, with , I'll get bounds on a, b, and c. That will leave me with 16 cases, which I can check directly.
Step 1. No prime greater than 7 divides n.
Suppose and the prime power occurs in the prime factorization of n. The formula in the second corollary tells us that there is at least a term in the product for . But since , I know that p is at least 11 (the next larger prime). Thus, , and so . Then
This is a contradiction, since the right side is larger than 8. Hence, no prime greater than 7 can divide n.
Step 2. .
If , then the formula in the second corollary tells us that there is at least a term in the product for . So I have
This is a contradiction, since .
At this point, I know that .
Step 3. and and .
Suppose . The factor is at least , but . Hence, .
Suppose . The factor is at least , so 3 divides the right side. But . Hence, .
Suppose . The factor is at least , so 5 divides the right side. But . Hence, .
At this point, I know and and . I could probably eliminate some possibilities by additional analysis, but with cases, I can just check by hand.
Step 4. Check the remaining cases by hand.
The numbers are 15, 20, 24, 30.
Appendix: An alternate proof of multiplicativity for
In this appendix, I'll give a direct proof of the multiplicativity of which doesn't use any results on arithmetic functions.
Theorem. If , then
Proof. I list the numbers from 1 to and count the number that are relatively prime to .
A typical column looks like:
Note that divides all the numbers in this column. Moreover, . Thus, if , then is a nontrivial divisor of each number in this column and of .
Hence, if , all the numbers in this column are not relatively prime to .
Therefore, since I'm counting numbers that are relatively prime to , I need only consider columns where . There are such columns.
So consider a column where . It contains the numbers
Start with , the standard residue system mod n. Since , multiplying by m produces another complete residue system:
Adding k must also give a complete residue system:
This is the column in question, so I've shown that such a column is a complete residue system mod n. It follows that of these numbers are relatively prime to n.
Thus, I have columns, all of whose elements are relatively prime to m, and in each such column of the elements are relatively prime to n. Thus, there are numbers in which are relatively prime to .
Let's look at how the proof works with a specific example. Take and . List the numbers from 1 to 36:
You can see that the columns beginning with 3, 6, and 9 --- the numbers k with --- contain only numbers that are not relatively prime to 9 (and hence, are not relatively prime to 36). Removing these columns, I have columns left: The ones beginning with 1, 2, 4, 5, 7, and 8.
Pick any one of those columns --- say the one beginning with 7, which contains . Note that these numbers reduce mod 4 to , which is a complete residue system mod 4. And exactly of these numbers --- in this case, 7 and 25 --- are relatively prime to 4.
Thus, there are numbers in which are relatively prime to , and so .
Bruce Ikenaga's Home Page
Copyright 2019 by Bruce Ikenaga