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:

thus,

* Lemma.*

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

So

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

(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 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

* 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, .

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

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,

* Corollary.* Let , and consider its prime factorization:

(Here the p's are distinct primes, and the r's are positive integers.) Then

Equivalently,

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

I have

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 .

Copyright 2019 by Bruce Ikenaga