# Arithmetic Functions and the Euler Phi Function

• An arithmetic function takes positive integers as inputs and produces real or complex numbers as outputs.
• If f is an arithmetic function, the divisor sum is the sum of the values of f at the positive divisors of n.
• is the number of positive divisors of n; is the sum of the positive divisors of n.
• The Möbius function is 1 if and 0 if n has a repeated prime factor. Otherwise, it is , where k is the number of (distinct) prime factors.
• The Dirichlet product of arithmetic functions f and g is .
• The Möbius inversion formula says that .
• .
• .
• The Euler phi function is multiplicative: If , then .

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),

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