Arithmetic Functions and the Euler Phi Function


I'm going to describe a formula for computing $\phi(n)$ 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 $f: \integer^+ \to \real$ by $f(n)
   = \sin n$ . Then f is an arithmetic function.

(b) The Euler phi function $\phi$ is an arithmetic function.

(c) Define $\tau: \integer^+ \to
   \integer^+$ by

$$\tau(n) = (\hbox{the number of positive divisors of n}).$$

For example, $\tau(12) = 6$ , since there are 6 positive divisors of 12 --- 1, 2, 3, 4, 6, and 12. $\tau$ is an arithmetic function.

(d) Define $\sigma: \integer^+ \to
   \integer^+$ by

$$\sigma(n) = (\hbox{the sum of the positive divisors of n}).$$

Since 1, 2, 3, 6, 9, and 18 are the positive divisors of 18,

$$\sigma(18) = 1 + 2 + 3 + 6 + 9 + 18 = 39.$$

$\sigma$ is an arithmetic function.


Definition. The Möbius function is the arithmetic function defined by $\mu(1) = 1$ , and for $n > 1$ ,

$$\mu(n) = \cases{(-1)^k & if $n = p_i\cdots p_k$, $p_i$ distinct primes \cr 0 & otherwise \cr}.$$

Thus, $\mu(n) = 0$ if n is divisible by a square.


Example. $\mu(6) = 1$ , since $6 = 2\cdot 3$ . Likewise, $\mu(30) = -1$ , since $30 = 2\cdot 3\cdot 5$ . But $\mu(12) = 0$ and $\mu(250 = 0$ .


Definition. If f is an arithmetic function, the divisor sum of f is

$$[D(f)](n) = \sum_{d \mid n} f(d).$$

To save writing, I'll make the convention that when I write "$\displaystyle \sum_{d\mid
   n}$ ", 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.

$$\hbox{\epsfxsize=2.5in \epsffile{phi-function1.eps}}\hskip0.25in \hbox{\epsfxsize=2.5in \epsffile{phi-function2.eps}}$$

$$\hbox{\epsfxsize=2.5in \epsffile{phi-function3.eps}}$$


Example. Suppose $f: \integer^+ \to \integer^+$ is defined by $f(n) = n^2$ . Then

$$[D(f)](n) = \sum_{d \mid n} d^2.$$

For example,

$$[D(f)](12) = \sum_{d \mid 12} d^2 = 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2 = 210.$$


Lemma.

$$[D(\mu)](n) = \sum_{d \mid n} \mu(d) = \cases{1 & if $n = 1$ \cr 0 & otherwise \cr}$$

Proof. The formula for $n = 1$ is obvious.

Suppose $n > 1$ . Let

$$n = p_1^{r_1}\cdots p_k^{r_k}$$

be the factorization of n into distinct primes. What are the nonzero terms in the sum $\displaystyle
   \sum_{d \mid n} \mu(d)$ ? They will come from d's which are products of single powers of $p_1$ , ... $p_k$ , and also $d = 1$ .

For example, $\mu(p_1p_2p_7)$ and $\mu(p_2p_4)$ would give rise to nonzero terms in the sum, but $\mu(p_3^3p_8) = 0$ .

So

$$\sum_{d \mid n} \mu(d) = 1 + \left(\mu(p_1) + \cdots + \mu(p_k)\right) + \left(\mu(p_1p_2) + \mu(p_1p_3) + \cdots + \mu(p_{k-1}p_k)\right) + \cdots + \mu(p_1p_2\cdots p_k) =$$

$$1 + {k \choose 1}(-1) + {k \choose 2}(-1)^2 + \cdots + {k \choose k}(-1)^k = (1 - 1)^k = 0.\quad\halmos$$


Example. Suppose $n = 24$ . The divisor sum is

$$\sum_{d \mid 24} \mu(d) = \mu(1) + \mu(2) + \mu(3) + \mu(4) + \mu(6) + \mu(12) + \mu(24) = 1 + (-1) + (-1) + 0 + 1 + 0 + 0 = 0.\quad\halmos$$


Definition. If f and g are arithmetic functions, their Dirichlet product is

$$(f\ast g)(n) = \sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right).$$


Example. If f and g are arithmetic functions,

$$(f\ast g)(12) = f(1)g(12) + f(2)g(6) + f(3)g(4) + f(4)(g(3) + f(6)g(2) + f(12)(g(1).\quad\halmos$$


I'll need two helper functions in what follows. Define

$$I(n) = 1 \quad\hbox{for all}\quad n \in \integer ^+,$$

$$e(n) = \cases{1 & if $n = 1$ \cr 0 & otherwise \cr} \quad\hbox{for all}\quad n \in \integer ^+.$$

Proposition. Let f, g, and h be arithmetic functions.

(a) $f\ast g = g\ast f$ .

(b) $(f\ast g)\ast h = f\ast
   (g\ast h)$ .

(c) $f\ast e = f = e\ast f$ .

(d) $f\ast I = Df = I\ast f$ .

(e) $\mu\ast I = e$ .

Proof. For (a), note that divisors of n come in pairs $\left\{d,
   \dfrac{n}{d}\right\}$ , and that if $\left\{d,
   \dfrac{n}{d}\right\}$ is a divisor pair, so is $\left\{\dfrac{n}{d}, d\right\}$ . This means that the same terms occur in both

$$(f\ast g)(n) = \sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right) \quad\hbox{and}\quad (g\ast f)(n) = \sum_{d\mid n} g(d)f\left(\dfrac{n}{d}\right).$$

Hence, they're equal.

Associativity is a little tedious, so I'll just note that $[(f\ast g)\ast h](n)$ and $[f\ast (g\ast h)](n)$ are equal to

$$\sum_{\{d,e,f\}} f(d)g(e)h(f).$$

Here the sum runs over all triples of positive numbers d, e, f such that $def = n$ . You can fill in the details.

For (c), note that

$$(f\ast e)(n) = \sum_{d\mid n} f(d)e\left(\dfrac{n}{d}\right) = f(n)e(1) = f(n).$$

($e\left(\dfrac{n}{d}\right)$ is 0 except when $\dfrac{n}{d} = 1$ , i.e. when $d =
   n$ .)

For (d),

$$(f\ast I)(n) = \sum_{d \mid n} f(d)I\left(\dfrac{n}{d}\right) = \sum_{d \mid n} f(d)\cdot 1 = \sum_{d \mid n} f(d) = (Df)(n).$$

For (e), start with $n = 1$ :

$$(\mu\ast I)(1) = \mu(1)I(1) = 1\cdot 1 = 1 = e(1).$$

Now suppose $n > 0$ . Then

$$(\mu\ast I)(n) = (D\mu)(n) = 0 = e(n).$$

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 $f = \mu\ast Df$ .

Proof.

$$\mu\ast Df = \mu\ast I\ast f = e\ast f = f.\quad\halmos$$

Next, I'll compute the divisor sum of the Euler phi function.

Lemma.

$$[D(\phi)](n) = \sum_{d \mid n} \phi(d) = n.$$

Proof. Let n be a positive integer. Construct the fractions

$$\dfrac{1}{n}, \quad \dfrac{2}{n}, \ldots, \dfrac{n - 1}{n}, \quad \dfrac{n}{n}.$$

Reduce them all to lowest terms. Consider a typical lowest-term fraction $\dfrac{a}{d}$ . Here $d \mid n$ (because it came from a fraction whose denominator was n, $a < d$ (because the original fraction was less than 1), and $(a,d) = 1$ (because it's in lowest terms).

Notice that (going the other way) if $\dfrac{a}{d}$ is a fraction with positive top and bottom which satisfies $d \mid n$ , $a < d$ , and $(a,d) = 1$ , then it is one of the lowest-terms fractions. For $dk = n$ for some k, and then $\dfrac{a}{d} = \dfrac{ka}{kd} =
   \dfrac{ka}{n}$ --- 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 $\phi(d)$ such fractions. Summing over all d's which divide n gives $\displaystyle \sum_{d \mid n}
   \phi(d)$ . 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, $\displaystyle \sum_{d \mid n} \phi(d) = n$ .


Example. Suppose $n = 6$ . Then

$$\sum_{d \mid 6} \phi(d) = \phi(1) + \phi(2) + \phi(3) + \phi(6) = 1 + 1 + 2 + 2 = 6.\quad\halmos$$


Lemma. Let $n \ge 1$ .

$$\phi(n) = \sum_{d \mid n} \mu(d) \dfrac{n}{d}.$$

Proof. By Möbius inversion and the previous result,

$$\phi(n) = (\mu\ast D\phi)(n) = \sum_{d \mid n} \mu(d) D\phi\left(\dfrac{n}{d}\right) = \sum_{d \mid n} \mu(d) \dfrac{n}{d}.\quad\halmos$$


Example. Take $n = 6$ , so $\phi(6) = 2$ .

$$\sum_{d \mid 6} \mu(d) \dfrac{6}{d} = \mu(1)\cdot \dfrac{6}{1} + \mu(2)\cdot \dfrac{6}{2} + \mu(3)\cdot \dfrac{6}{3} + \mu(6)\cdot \dfrac{6}{6} =$$

$$(1)(6) + (-1)(3) + (-1)(2) + (1)(1) = 2.\quad\halmos$$


Theorem. Let $n \ge 1$ .

$$\phi(n) = n\cdot \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right)$$

(By convention, the empty product --- the product with no terms --- equals 1.)

Proof. If $n = 1$ , the result is immediate by convention.

If $n > 1$ , let $p_1$ , ..., $p_k$ be the distinct prime factors of n. Then

$$\prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right) = \left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right) \cdots \left(1 - \dfrac{1}{p_k}\right) =$$

$$1 - \sum_i \dfrac{1}{p_i} + \sum_{i \ne j} \dfrac{1}{p_ip_j} - \cdots + (-1)^k \dfrac{1}{p_1p_2\cdots p_k}.$$

Each term is $\pm \dfrac{1}{d}$ , where d is 1 (the first term) or a product of distinct primes. The $(-1)^i$ 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

$$\sum_{d\mid n} \dfrac{\mu(d)}{d}.$$

(I can run the sum over all divisors, because $\mu(d) = 0$ if d has a repeated prime factor.) Now simply multiply by n:

$$n\cdot \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right) = \sum_{d \mid n} \mu(d) \dfrac{n}{d} = \phi(n).\quad\halmos$$


Example. $40 = 2^3\cdot 5$ , so

$$\phi(40) = 40\left(1 - \dfrac{1}{2}\right) \left(1 - \dfrac{1}{5}\right) = 16.$$

Likewise, $81 = 3^4$ , so

$$\phi(81) = 81\cdot \left(1 - \dfrac{1}{3}\right) = 54.$$

More generally, if p is prime and $k \ge 1$ , then

$$\phi(p^k) = p^k - p^{k-1}.$$

For

$$\phi(p^k) = p^k\cdot \left(1 - \dfrac{1}{p}\right) = p^k - p^{k-1}.\quad\halmos$$


Definition. An arithmetic function f is multiplicative if $(m,n) = 1$ implies

$$f(mn) = f(m)f(n).$$

Lemma. $\phi$ is multiplicative --- that is, if $(m,n) = 1$ , then

$$\phi(mn) = \phi(m)\phi(n).$$

Proof. Suppose $(m,n) = 1$ . Now

$$\phi(m) = m\cdot \prod_{{p \mid m}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right) \quad\hbox{and}\quad \phi(n) = n\cdot \prod_{{q \mid n}\atop{q\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{q}\right).$$

So

$$\dfrac{\phi(m)\phi(n)}{mn} = \left(\prod_{{p \mid m}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right)\right) \left(\prod_{{q \mid n}\atop{q\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{q}\right)\right).$$

Since $(m,n) = 1$ , the two products have no primes in common. Moreover, the primes that appear in either of the products are exactly the prime factors of $mn$ . So

$$\dfrac{\phi(m)\phi(n)}{mn} = \prod_{{r \mid mn}\atop{r\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{r}\right).$$

Hence,

$$\phi(m)\phi(n) = (mn)\cdot \prod_{{r \mid mn}\atop{r\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{r}\right) = \phi(mn).\quad\halmos$$


Example. If $n \ge 3$ , then $\phi(n)$ is even. In fact, if n has k odd prime factors, then $2^k \mid \phi(n)$ .

To see this, observe first that

$$\phi(2^k) = 2^k - 2^{k-1}.$$

This is even if $2^k \ge 4$ .

So suppose that n has k odd prime factors. Then

$$\phi(n) = n\cdot \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(1 - \dfrac{1}{p}\right) = \phi(n) = n\cdot \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(\dfrac{p - 1}{p}\right) = \dfrac{n}{\displaystyle \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} p} \prod_{{p \mid n}\atop{p\ \hbox{\fiverm prime}}} \left(p - 1\right).$$

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 $p - 1$ is even. Hence, the second term --- and therefore $\phi(n)$ --- is divisible by $2^k$ .

For example, consider $7623 =
   3^2\cdot 7\cdot 11^2$ . There are 3 odd prime factors, so $\phi(7623)$ should be divisible by 8. And in fact, $\phi(7623) = 3960 = 8\cdot 495$ .


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga