Contents / Number Theory / Arithmetic Functions

Chapter 4

Arithmetic Functions

Dirichlet convolution and the ring it makes, with multiplicativity preserved under convolution as the engine of the chapter; Euler's totient derived three ways; the Mobius function, the key identity, and inversion in both directions as a convolution statement; sigma_k and the Euclid-Euler characterisation of even perfect numbers; the Carmichael function and Korselt's criterion; and Mertens' theorems.

Introduction

An arithmetic function is nothing more than a function $f : Z^{+} \to C$ . Stated that baldly the definition promises nothing: every sequence is an arithmetic function, and there is no theory of arbitrary sequences. What makes the subject is a single structural observation — the positive integers are not merely ordered, they factor — and the functions worth studying are the ones that notice.

The chapter is organised around that observation and around one operation. The operation is Dirichlet convolution,

(f * g) (n) = d ∣ n \sum f (d) g (n / d),

which sums over the factorisations of $n$ rather than over its predecessors. Under it the arithmetic functions form a commutative ring with identity, invertible elements and all; the multiplicative functions form a group inside that ring; and almost every classical identity in the subject — Euler's $\sum_{d ∣ n} φ (d) = n$ , Möbius inversion, the formula $σ_{k} = id^{k} * u$ — is a single line of algebra in that ring once the ring is built. Building it is therefore the first order of business, and the two facts that do the work, associativity and the multiplicativity of a convolution of multiplicative functions, are proved in full.

With the algebra in place the classical functions follow quickly: the totient $φ$ , the Möbius function $μ$ , the divisor functions $σ_{k}$ , the Carmichael function $λ$ . Each is introduced by what it counts, then computed from the prime factorisation, then related to the others by a convolution identity. Two named theorems get complete proofs — the Euclid–Euler classification of even perfect numbers, and Korselt's criterion for Carmichael numbers — because both are cases where a purely elementary argument settles a question that looks as though it should need machinery.

The last lesson is about size rather than structure. The functions here oscillate violently: $φ (n) / n$ comes arbitrarily close to $0$ and infinitely often equals $1 - 1/ n$ ; $d (n)$ is $2$ infinitely often and unbounded. What is stable is their average behaviour, and Mertens' three theorems are the sharpest elementary statements about how the primes distribute themselves in that average. Two of the three are proved here from Chebyshev-type estimates; the third needs the prime number theorem for its constant, and where that happens the argument is explicitly labelled a sketch.

Throughout, $p$ always denotes a prime, $d ∣ n$ means $d$ runs over the positive divisors of $n$ , and $n = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ is the prime factorisation of $n > 1$ with the $p_{i}$ distinct and $a_{i} \geq 1$ . Unique factorisation is assumed throughout, as developed in Fundamental Theorem of Arithmetic.

4.1Definitions and basic classes

A warning about terminology before anything else. In number theory "additive" and "multiplicative" do not describe behaviour under $m + n$ . Both describe behaviour under multiplication, and they differ only in whether the values are combined by $+$ or by $\times$ . The convention is historical and unhelpful, and it is universal.

Definition 4.1 (Arithmetic function). An arithmetic function is a function $f : Z^{+} \to C$ . Two arithmetic functions are equal when they agree at every positive integer.

Definition 4.2 (Additive and multiplicative). An arithmetic function $f$ is

additive if $f (mn) = f (m) + f (n)$ whenever $g cd (m, n) = 1$ ;
completely additive if $f (mn) = f (m) + f (n)$ for all $m, n$ ;
multiplicative if $f$ is not identically zero and $f (mn) = f (m) f (n)$ whenever $g cd (m, n) = 1$ ;
completely multiplicative if $f$ is not identically zero and $f (mn) = f (m) f (n)$ for all $m, n$ .

The coprimality hypothesis is the whole point. It says the value of $f$ at $n$ is determined by its values at the prime powers $p_{i}^{a_{i}}$ , because those are pairwise coprime and multiply to $n$ . A multiplicative function is thus a function on prime powers that has been extended to all integers in the only consistent way, and specifying one means specifying a doubly-indexed table of numbers $f (p^{a})$ and nothing else.

Proposition 4.3 (Normalisation at $1$ ). If $f$ is multiplicative then $f (1) = 1$ . If $f$ is additive then $f (1) = 0$ .

Proof. Since $g cd (1, 1) = 1$ , multiplicativity gives $f (1) = f (1 \cdot 1) = f (1)^{2}$ , so $f (1) \in {0, 1}$ . If $f (1) = 0$ then for every $n$ , $g cd (n, 1) = 1$ gives $f (n) = f (n) f (1) = 0$ , so $f$ is identically zero, which the definition excludes. Hence $f (1) = 1$ . In the additive case the same computation reads $f (1) = 2 f (1)$ , so $f (1) = 0$ ; no exclusion is needed because the zero function is additive and harmless.∎

Theorem 4.4 (A multiplicative function is determined by its prime powers). Let $f$ be multiplicative and let $n = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ . Then

f (n) = i = 1 \prod r f (p_{i}^{a_{i}}) .

Conversely, given any values $c_{p, a} \in C$ indexed by primes $p$ and exponents $a \geq 1$ , the formula $f (n) = \prod_{i} c_{p_{i}, a_{i}}$ , together with $f (1) = 1$ , defines a multiplicative function.

Proof. For the first claim, induct on $r$ . When $r = 0$ the empty product is $1 = f (1)$ by Normalisation at $1$ , and $r = 1$ is trivial. For $r > 1$ put $m = p_{1}^{a_{1}}$ and $n^{'} = p_{2}^{a_{2}} \dots p_{r}^{a_{r}}$ . No prime divides both $m$ and $n^{'}$ , so $g cd (m, n^{'}) = 1$ and multiplicativity gives $f (n) = f (m) f (n^{'})$ ; the inductive hypothesis expands $f (n^{'})$ .

For the converse, let $g cd (m, n) = 1$ . No prime occurs in both factorisations, so the factorisation of $mn$ is the concatenation of those of $m$ and $n$ with the exponents carried over unchanged. The product defining $f (mn)$ therefore splits as the product for $f (m)$ times the product for $f (n)$ . Finally $f (1) = 1 \neq = 0$ , so $f$ is not identically zero.∎

The converse half is what licenses the standard style of proof in this chapter: to prove two multiplicative functions equal, check them on prime powers. Everything else is bookkeeping done once and for all.

Example 4.5 (Recognising the classes). Classify $ω (n)$ (the number of distinct primes dividing $n$ ), $Ω (n)$ (the number of prime factors counted with multiplicity), $id (n) = n$ , and $d (n)$ (the number of positive divisors).

Solution.

$ω$ is additive: for coprime $m, n$ the prime sets are disjoint, so $ω (mn) = ω (m) + ω (n)$ . It is not completely additive, since $ω (4) = 1$ but $ω (2) + ω (2) = 2$ .
$Ω$ is completely additive: exponents simply add when any two integers are multiplied, coprime or not.
$id$ is completely multiplicative, since $mn = mn$ with no hypothesis at all.
$d$ is multiplicative — this is proved below as Divisors of a coprime product — but not completely multiplicative: $d (4) = 3$ while $d (2) d (2) = 4$ .

□

Proposition 4.6 (Divisors of a coprime product). If $g cd (m, n) = 1$ then every divisor $e$ of $mn$ factors uniquely as $e = e_{1} e_{2}$ with $e_{1} ∣ m$ and $e_{2} ∣ n$ , and the map $(e_{1}, e_{2}) \mapsto e_{1} e_{2}$ is a bijection from divisors of $m$ paired with divisors of $n$ onto the divisors of $mn$ . Consequently $d$ is multiplicative.

Proof. Set $e_{1} = g cd (e, m)$ and $e_{2} = g cd (e, n)$ . Since $g cd (m, n) = 1$ we have $g cd (e_{1}, e_{2}) = 1$ , and both divide $e$ , so $e_{1} e_{2} ∣ e$ . Conversely write $e = \prod p^{c_{p}}$ with $c_{p} \leq a_{p} + b_{p}$ where $p^{a_{p}} ∥ m$ and $p^{b_{p}} ∥ n$ ; coprimality forces $a_{p} = 0$ or $b_{p} = 0$ for each $p$ , so $c_{p} \leq a_{p}$ or $c_{p} \leq b_{p}$ , meaning each prime power of $e$ lands entirely in $e_{1}$ or entirely in $e_{2}$ . Hence $e ∣ e_{1} e_{2}$ and so $e = e_{1} e_{2}$ .

The map $(e_{1}, e_{2}) \mapsto e_{1} e_{2}$ is injective because $e_{1} = g cd (e_{1} e_{2}, m)$ recovers $e_{1}$ from the product, again using $g cd (e_{2}, m) = 1$ ; and it is surjective by the previous paragraph. Counting both sides gives $d (mn) = d (m) d (n)$ , and $d (1) = 1$ , so $d$ is multiplicative.∎

Remark. The bijection above is the reason so many proofs in this chapter look the same. Whenever a quantity is defined as a sum over divisors of $n$ , splitting $n$ into coprime parts splits the sum into a product of two sums, because the index set itself splits as a product. That single observation is upgraded into the theorem Convolution preserves multiplicativity later in the chapter.

Definition 4.7 (The basic functions). Four arithmetic functions recur constantly:

ε (n) = {10 n = 1, n > 1, u (n) = 1, id_{k} (n) = n^{k}, id = id_{1} .

The function $ε$ is the delta function (or unit function); $u$ is the constant one.

All four are completely multiplicative. For $ε$ this is a small surprise worth checking: $ε (mn) = ε (m) ε (n)$ holds for all $m, n$ because both sides are $1$ when $m = n = 1$ and $0$ otherwise. The property that actually matters about $ε$ , however, is not its multiplicativity but the fact — proved in the lesson Dirichlet convolution — that it is the identity element for convolution.

Exercises for §4.1 →

4.2Values, order of magnitude, and the ring structure

Before convolution there are the two obvious operations. Arithmetic functions can be added and multiplied pointwise, since their values are complex numbers, and under those operations they form a commutative ring — a completely uninteresting one, isomorphic to a countable product of copies of $C$ , riddled with zero divisors and carrying no arithmetic information whatever. It is worth stating precisely once, because the contrast with the Dirichlet ring is the point.

Proposition 4.8 (The pointwise ring). Under $(f + g) (n) = f (n) + g (n)$ and $(f \cdot g) (n) = f (n) g (n)$ , the set $A$ of arithmetic functions is a commutative ring with identity $u$ . Its zero divisors are exactly the functions vanishing somewhere without vanishing identically, and its units are exactly the nowhere-zero functions.

Proof. Every axiom is checked at each $n$ separately, where it is an axiom of $C$ ; the identity is the function constantly $1$ , namely $u$ . If $f$ vanishes at some $m$ and $g$ is any function supported at $m$ alone, then $f g = 0$ while neither factor need be zero, giving a zero divisor; and if $f$ is nowhere zero then $n \mapsto f (n)^{- 1}$ is a pointwise inverse. Conversely a unit cannot vanish anywhere, since $f (n) g (n) = 1$ forces $f (n) \neq = 0$ .∎

Remark. Pointwise multiplication destroys multiplicativity in no way — a pointwise product of multiplicative functions is multiplicative — but it is useless for identities like $\sum_{d ∣ n} φ (d) = n$ , which relate a function's values at $n$ to its values at the divisors of $n$ . Nothing in the pointwise ring looks at divisors. Dirichlet convolution is the operation that does, and it is introduced in the lesson Dirichlet convolution.

Two more operations appear often enough to be named: the summatory function and the Dirichlet series, treated in the next section. The summatory function is the bridge to analysis.

Definition 4.9 (Summatory function). The summatory function of $f$ is

F (x) = n \leq x \sum f (n), x \geq 1,

the sum running over positive integers $n$ not exceeding $x$ .

Individual values of a multiplicative function jump around: $d (n)$ is $2$ at every prime and exceeds $100$ infinitely often, and no asymptotic formula for $d (n)$ itself can exist. The summatory function smooths that out, and it is where all the asymptotic statements of the subject live. The basic tool for computing one is the exchange of order in a double sum, which deserves to be stated as a lemma because every later estimate uses it.

Lemma 4.10 (Dirichlet hyperbola exchange). For any arithmetic function $f$ and any $x \geq 1$ ,

n \leq x \sum d ∣ n \sum f (d) = d \leq x \sum f (d) ⌊ \frac{x}{d} ⌋ .

Proof. Both sides count the same set of pairs $(d, q)$ of positive integers with $d q \leq x$ , weighted by $f (d)$ . On the left the outer index is $n = d q$ and the inner index is $d ∣ n$ ; on the right the outer index is $d$ and the inner count is the number of $q$ with $q \leq x / d$ , which is $⌊ x / d ⌋$ . Since $f (d)$ does not depend on $q$ , the inner sum on the right is $f (d)$ times that count.∎

Example 4.11 (The average number of divisors). Use the exchange lemma to show $\sum_{n \leq x} d (n) = x ln x + O (x)$ .

Solution.

Since $d (n) = \sum_{d ∣ n} 1$ , the lemma with $f = u$ gives $\sum_{n \leq x} d (n) = \sum_{d \leq x} ⌊ x / d ⌋$ .
Write $⌊ x / d ⌋ = x / d + O (1)$ ; the error terms contribute $O (x)$ in total, since there are at most $x$ of them.
The main term is $x \sum_{d \leq x} 1/ d = x (ln x + O (1))$ , using the harmonic sum estimate.
Combining, $\sum_{n \leq x} d (n) = x ln x + O (x)$ , so the average number of divisors of an integer near $x$ is about $ln x$ even though no individual value is predictable.

□

Remark. The error term here can be improved a great deal — the hyperbola method gives $x ln x + (2 γ - 1) x + O (x)$ , and the true exponent in the error is the subject of the unsolved Dirichlet divisor problem. The crude version above is enough for everything in this chapter.

Exercises for §4.2 →

4.3Generating functions and Dirichlet series

An arithmetic function has two natural generating objects. The ordinary power series $\sum f (n) x^{n}$ is the right tool for additive structure — it turns $n \mapsto n + 1$ into multiplication by $x$ — and is almost useless here. The right object is the Dirichlet series, which turns the multiplicative structure into an Euler product.

Definition 4.12 (Dirichlet series). The Dirichlet series of an arithmetic function $f$ is the formal series

D_{f} (s) = n = 1 \sum \infty \frac{f ( n )}{n ^{s}} .

When $f = u$ this is the Riemann zeta function $ζ (s) = \sum_{n \geq 1} n^{- s}$ , convergent for $Re (s) > 1$ .

The reason this is the right transform is one line of algebra: $n^{- s} m^{- s} = (nm)^{- s}$ . Multiplying two Dirichlet series therefore collects terms according to factorisations, exactly the way convolution does.

Theorem 4.13 (Dirichlet series multiply by convolution). For arithmetic functions $f, g$ ,

D_{f} (s) D_{g} (s) = D_{f * g} (s), (f * g) (n) = d ∣ n \sum f (d) g (n / d),

as an identity of formal Dirichlet series, and as an identity of functions wherever both series converge absolutely.

Proof. Formally, multiply out:

(a \geq 1 \sum \frac{f ( a )}{a ^{s}}) (b \geq 1 \sum \frac{g ( b )}{b ^{s}}) = a, b \geq 1 \sum \frac{f ( a ) g ( b )}{( ab ) ^{s}} = n \geq 1 \sum \frac{1}{n ^{s}} ab = n \sum f (a) g (b),

and the inner sum is $\sum_{d ∣ n} f (d) g (n / d) = (f * g) (n)$ , since the pairs $(a, b)$ with $ab = n$ are exactly the pairs $(d, n / d)$ with $d ∣ n$ . When both series converge absolutely at $s$ , the double series converges absolutely, so the rearrangement collecting terms with $ab = n$ is legitimate by Fubini's theorem for series, and the identity holds as one between complex numbers.∎

This theorem is the dictionary for the rest of the chapter. Every convolution identity proved later has a Dirichlet series shadow, and it is usually the shadow one remembers: $σ_{k} = id_{k} * u$ becomes $\sum σ_{k} (n) n^{- s} = ζ (s) ζ (s - k)$ , and the Möbius identity $μ * u = ε$ becomes $\sum μ (n) n^{- s} = 1/ ζ (s)$ .

Theorem 4.14 (Euler product). Let $f$ be multiplicative with $\sum_{n} ∣ f (n) ∣ n^{- σ} < \infty$ . Then

D_{f} (s) = p \prod (1 + \frac{f ( p )}{p ^{s}} + \frac{f ( p ^{2} )}{p ^{2 s}} + \dots)

for $Re (s) = σ$ , the product over all primes. If $f$ is completely multiplicative the inner series is geometric and

D_{f} (s) = p \prod (1 - \frac{f ( p )}{p ^{s}})^{- 1} .

Proof. Let $P$ be a finite set of primes and expand the finite product $\prod_{p \in P} \sum_{a \geq 0} f (p^{a}) p^{- a s}$ . By absolute convergence the product of the inner series may be expanded term by term, and a general term is $\prod_{p \in P} f (p^{a_{p}}) p^{- a_{p} s} = f (n) n^{- s}$ where $n = \prod_{p \in P} p^{a_{p}}$ , the equality of coefficients being A multiplicative function is determined by its prime powers. Distinct exponent vectors give distinct $n$ by unique factorisation, so the finite product equals $\sum_{n \in S (P)} f (n) n^{- s}$ where $S (P)$ is the set of integers all of whose prime factors lie in $P$ .

Now take $P = {p : p \leq N}$ . Every $n \leq N$ lies in $S (P)$ , so the difference between $D_{f} (s)$ and the finite product is bounded by $\sum_{n > N} ∣ f (n) ∣ n^{- σ}$ , the tail of a convergent series, which tends to $0$ . Hence the products converge to $D_{f} (s)$ . For completely multiplicative $f$ , $f (p^{a}) = f (p)^{a}$ and $\sum_{a} (f (p) p^{- s})^{a} = (1 - f (p) p^{- s})^{- 1}$ , the ratio having modulus $∣ f (p) ∣ p^{- σ} < 1$ because the single term $n = p$ of a convergent series of non-negative terms is less than $1$ for all but finitely many $p$ , and for the remaining finitely many the hypothesis of absolute convergence forces it too.∎

Corollary 4.15 (Euler's product for zeta). For $Re (s) > 1$ ,

ζ (s) = p \prod (1 - p^{- s})^{- 1} .

In particular $ζ (s) \neq = 0$ in that half-plane.

Proof. Apply Euler product to the completely multiplicative function $u$ , for which $\sum_{n} n^{- σ}$ converges when $σ > 1$ . Non-vanishing follows because a convergent infinite product of nonzero factors is nonzero: each factor $(1 - p^{- s})^{- 1}$ is a nonzero complex number, and the partial products converge to $ζ (s)$ while their reciprocals $\prod_{p \leq N} (1 - p^{- s})$ converge to a finite limit, so $ζ (s)$ cannot be $0$ .∎

Intuition. The Euler product is unique factorisation, written as an equation between infinite sums. Choosing a term from each bracket is choosing an exponent for each prime; multiplying them out and collecting is exactly the statement that each integer arises from exactly one such choice.

Example 4.16 (The Dirichlet series of $d$ and of $σ$ ). Write $\sum_{n \geq 1} d (n) n^{- s}$ and $\sum_{n \geq 1} σ (n) n^{- s}$ in terms of $ζ$ .

Solution.

$d = u * u$ , since $\sum_{d ∣ n} 1 \cdot 1 = d (n)$ . By Dirichlet series multiply by convolution, $\sum d (n) n^{- s} = ζ (s)^{2}$ , valid for $Re (s) > 1$ .
$σ = id * u$ , since $\sum_{d ∣ n} d = σ (n)$ . The Dirichlet series of $id$ is $\sum n \cdot n^{- s} = \sum n^{- (s - 1)} = ζ (s - 1)$ .
Hence $\sum σ (n) n^{- s} = ζ (s) ζ (s - 1)$ , valid for $Re (s) > 2$ so that both factors converge absolutely.

□

Exercises for §4.3 →

4.4Multiplicative functions in practice

The definition of multiplicativity was given in Additive and multiplicative, and the theorem A multiplicative function is determined by its prime powers reduced every multiplicative function to a table of values $f (p^{a})$ . This section is about using that reduction: how to decide whether a given function is multiplicative, and how to read off its values once it is.

The practical test has two halves. To prove multiplicativity, exhibit the function as a count of something that splits across coprime parts, or as a convolution of functions already known to be multiplicative. To disprove it, one counterexample suffices — and the cheapest counterexample is almost always a comparison of $f (p^{2})$ against $f (p)^{2}$ , which tests complete multiplicativity, or of $f (6)$ against $f (2) f (3)$ , which tests the real thing.

Example 4.17 (Which of these are multiplicative?). Decide whether each of $f (n) = n + 1$ , $g (n) = 2^{ω (n)}$ , $h (n) = g cd (n, 12)$ is multiplicative.

Solution.

$f (n) = n + 1$ : $f (1) = 2 \neq = 1$ , so it fails Normalisation at $1$ immediately and is not multiplicative.
$g (n) = 2^{ω (n)}$ : $ω$ is additive, so for coprime $m, n$ , $g (mn) = 2^{ω (m) + ω (n)} = g (m) g (n)$ , and $g (1) = 2^{0} = 1$ . Multiplicative. It is not completely multiplicative: $g (4) = 2$ but $g (2)^{2} = 4$ .
$h (n) = g cd (n, 12)$ : take $m = 4$ , $n = 3$ . Then $h (12) = 12$ while $h (4) h (3) = 4 \cdot 3 = 12$ . That case works; in fact $g cd (n, N)$ is multiplicative in $n$ for any fixed $N$ , because $g cd (mn, N) = g cd (m, N) g cd (n, N)$ when $g cd (m, n) = 1$ , each prime power of $N$ being captured by exactly one of $m$ , $n$ .

□

Proposition 4.18 (Exponentiating an additive function). If $g$ is additive then $f (n) = c^{g (n)}$ is multiplicative for any constant $c \neq = 0$ ; if $g$ is completely additive then $f$ is completely multiplicative.

Proof. For coprime $m, n$ , $f (mn) = c^{g (mn)} = c^{g (m) + g (n)} = c^{g (m)} c^{g (n)} = f (m) f (n)$ , and $f (1) = c^{g (1)} = c^{0} = 1$ by Normalisation at $1$ , so $f$ is not identically zero. Dropping the coprimality hypothesis on $g$ drops it on $f$ , giving the second claim.∎

Corollary 4.19 (The Liouville function). The Liouville function $λ_{L} (n) = (- 1)^{Ω (n)}$ is completely multiplicative.

Proof. $Ω$ is completely additive, as observed in Recognising the classes, so Exponentiating an additive function applies with $c = - 1$ .∎

Pitfall. A multiplicative function need not be positive, need not be monotone, and need not be determined by finitely much data. The one thing it is determined by is its table on prime powers — and two multiplicative functions agreeing on all primes may still differ, because they can differ at $p^{2}$ . Checking an identity at primes only is the most common error in the subject.

Proposition 4.20 (Products and quotients). If $f$ and $g$ are multiplicative then so is the pointwise product $f g$ , and so is $f / g$ provided $g$ is nowhere zero. The pointwise sum $f + g$ is in general not multiplicative.

Proof. For coprime $m, n$ : $(f g) (mn) = f (mn) g (mn) = f (m) g (m) f (n) g (n) = (f g) (m) (f g) (n)$ , and $(f g) (1) = 1$ . The same computation with $g (mn)^{- 1}$ gives the quotient. For the last claim, $(f + g) (1) = f (1) + g (1) = 2 \neq = 1$ , so a sum of two multiplicative functions is never multiplicative.∎

Example 4.21 (Reading values off the table). Let $f$ be multiplicative with $f (p^{a}) = a + 1$ for every prime $p$ and every $a \geq 1$ . Compute $f (360)$ and identify $f$ .

Solution.

$360 = 2^{3} \cdot 3^{2} \cdot 5$ .
By A multiplicative function is determined by its prime powers, $f (360) = f (2^{3}) f (3^{2}) f (5) = 4 \cdot 3 \cdot 2 = 24$ .
The number of divisors of $p^{a}$ is $a + 1$ , so $f$ agrees with $d$ on all prime powers, and two multiplicative functions agreeing on prime powers are equal. Hence $f = d$ , and indeed $d (360) = 24$ .

□

Exercises for §4.4 →

4.5Convolution preserves multiplicativity

This is the engine of the chapter. Every classical multiplicative function below is built by convolving simpler ones, and the reason each is multiplicative is the single theorem proved here. It deserves a careful proof because the two hypotheses — that $f$ and $g$ are multiplicative, and that the divisors of a coprime product factor — enter at different points, and seeing where is what makes the result usable.

Theorem 4.22 (Convolution preserves multiplicativity). If $f$ and $g$ are multiplicative, then so is $f * g$ , where

(f * g) (n) = d ∣ n \sum f (d) g (n / d) .

Proof. First, $(f * g) (1) = f (1) g (1) = 1 \neq = 0$ , so $f * g$ is not identically zero.

Now let $g cd (m, n) = 1$ . By Divisors of a coprime product, every divisor $e$ of $mn$ is uniquely $e = e_{1} e_{2}$ with $e_{1} ∣ m$ , $e_{2} ∣ n$ , and every such pair arises. Reindexing the sum over $e ∣ mn$ as a double sum over the pairs,

(f * g) (mn) = e_{1} ∣ m \sum e_{2} ∣ n \sum f (e_{1} e_{2}) g (\frac{mn}{e _{1} e _{2}}) .

Two coprimality facts now apply. Since $e_{1} ∣ m$ and $e_{2} ∣ n$ and $g cd (m, n) = 1$ , we have $g cd (e_{1}, e_{2}) = 1$ , so $f (e_{1} e_{2}) = f (e_{1}) f (e_{2})$ . Likewise $m / e_{1}$ divides $m$ and $n / e_{2}$ divides $n$ , so $g cd (m / e_{1}, n / e_{2}) = 1$ and

g (\frac{mn}{e _{1} e _{2}}) = g (\frac{m}{e _{1}} \cdot \frac{n}{e _{2}}) = g (\frac{m}{e _{1}}) g (\frac{n}{e _{2}}) .

Substituting both and separating the variables, the double sum factors:

(f * g) (mn) = e_{1} ∣ m \sum f (e_{1}) g (m / e_{1}) e_{2} ∣ n \sum f (e_{2}) g (n / e_{2}) = (f * g) (m) (f * g) (n) .

∎

Remark. Note what was not assumed: nothing about complete multiplicativity, and nothing about convergence, since every sum is finite. Note also what fails: a convolution of two completely multiplicative functions is usually not completely multiplicative. $u * u = d$ and $d (4) = 3 \neq = 4 = d (2)^{2}$ .

Corollary 4.23 (Local factors of a convolution). If $f, g$ are multiplicative then for every prime power $p^{a}$ ,

(f * g) (p^{a}) = j = 0 \sum a f (p^{j}) g (p^{a - j}),

and $f * g$ is determined by these values.

Proof. The divisors of $p^{a}$ are exactly $1, p, \dots, p^{a}$ by unique factorisation, which is the stated sum. Determination is A multiplicative function is determined by its prime powers applied to $f * g$ , which is multiplicative by Convolution preserves multiplicativity.∎

This corollary is the computational form of the theorem. To identify a convolution it is enough to evaluate one finite sum at each prime power, and that sum is usually a geometric series or a telescoping one.

Example 4.24 (Identifying $u * id$ at a prime power). Compute $(u * id) (p^{a})$ and hence give a closed formula for $σ (n) = \sum_{d ∣ n} d$ .

Solution.

By Local factors of a convolution, $(u * id) (p^{a}) = \sum_{j = 0}^{a} 1 \cdot p^{j} = 1 + p + \dots + p^{a}$ .
Summing the geometric series, this is $(p^{a + 1} - 1) / (p - 1)$ .
Since $u * id$ is multiplicative, $σ (n) = \prod_{i} \frac{p _{i}^{a_{i} + 1} - 1}{p _{i} - 1}$ .
Check: $σ (12) = \frac{2 ^{3} - 1}{1} \cdot \frac{3 ^{2} - 1}{2} = 7 \cdot 4 = 28$ , and indeed $1 + 2 + 3 + 4 + 6 + 12 = 28$ .

□

Example 4.25 (A convolution that collapses). Let $f$ be the multiplicative function with $f (p^{a}) = 1$ for $a = 1$ and $f (p^{a}) = 0$ for $a \geq 2$ ; that is, $f (n) = 1$ if $n$ is squarefree and $0$ otherwise. Compute $(f * f) (p^{a})$ for $a = 0, 1, 2, 3$ .

Solution.

$a = 0$ : the only term is $f (1) f (1) = 1$ .
$a = 1$ : $f (1) f (p) + f (p) f (1) = 1 + 1 = 2$ .
$a = 2$ : $f (1) f (p^{2}) + f (p) f (p) + f (p^{2}) f (1) = 0 + 1 + 0 = 1$ .
$a = 3$ : $f (1) f (p^{3}) + f (p) f (p^{2}) + f (p^{2}) f (p) + f (p^{3}) f (1) = 0$ .
So $(f * f) (n)$ counts the ways to write $n$ as an ordered product of two squarefree numbers, and it vanishes as soon as some prime occurs to the third power or higher.

□

Exercises for §4.5 →

4.6Euler products for multiplicative functions

The theorem Euler product says that the Dirichlet series of a multiplicative function factors over the primes. In practice one rarely needs the analytic statement; one needs the bookkeeping, which is that a local factor

E_{p} (f, s) = a \geq 0 \sum \frac{f ( p ^{a} )}{p ^{a s}}

can be computed for each prime separately, and the answer for the whole function is the product. The art is recognising a local factor as a ratio of zeta values, because then the whole series is a ratio of zeta functions and its analytic behaviour is known.

Proposition 4.26 (The series of $μ$ , $d$ and $σ_{k}$ ). For $Re (s)$ large enough for absolute convergence,

n \geq 1 \sum \frac{μ ( n )}{n ^{s}} = \frac{1}{ζ ( s )}, n \geq 1 \sum \frac{d ( n )}{n ^{s}} = ζ (s)^{2}, n \geq 1 \sum \frac{σ _{k} ( n )}{n ^{s}} = ζ (s) ζ (s - k) .

Proof. Each is Dirichlet series multiply by convolution applied to a convolution identity established elsewhere in the chapter. For the first, $μ * u = ε$ by The Möbius sum identity, and $D_{ε} (s) = 1$ since $ε$ is supported at $n = 1$ ; so $D_{μ} (s) ζ (s) = 1$ . For the second, $d = u * u$ . For the third, $σ_{k} = id_{k} * u$ by Divisor-power sums as a convolution, and $D_{id_{k}} (s) = \sum n^{k - s} = ζ (s - k)$ . Absolute convergence holds for $Re (s) > 1$ in the first two cases and $Re (s) > max (1, k + 1)$ in the third, since $σ_{k} (n) \leq n^{k} d (n) \leq n^{k + 1}$ .∎

Example 4.27 (Counting squarefree integers). Let $Q (n) = 1$ if $n$ is squarefree and $0$ otherwise. Compute the Euler product and Dirichlet series of $Q$ , and deduce the density of squarefree integers.

Solution.

$Q$ is multiplicative with $Q (p^{0}) = Q (p) = 1$ and $Q (p^{a}) = 0$ for $a \geq 2$ , so the local factor is $E_{p} (Q, s) = 1 + p^{- s}$ .
Hence $\sum Q (n) n^{- s} = \prod_{p} (1 + p^{- s})$ . Multiplying and dividing by $(1 - p^{- s})$ gives $1 + p^{- s} = (1 - p^{- 2 s}) / (1 - p^{- s})$ , so the product is $ζ (s) / ζ (2 s)$ .
The density of squarefree integers is governed by the residue of that series at $s = 1$ , which is $1/ ζ (2) = 6/ π^{2} \approx 0.6079$ .
So about $60.8%$ of integers are squarefree — a figure the local factors deliver with no analysis beyond knowing $ζ (2) = π^{2} /6$ .

□

Proposition 4.28 (A completely multiplicative function has a one-term local factor). $f$ is completely multiplicative if and only if its local factors are all geometric, $E_{p} (f, s) = (1 - f (p) p^{- s})^{- 1}$ , equivalently $f (p^{a}) = f (p)^{a}$ for every prime power.

Proof. If $f$ is completely multiplicative, $f (p^{a}) = f (p)^{a}$ by induction on $a$ , and summing the geometric series gives the stated factor. Conversely, if $f (p^{a}) = f (p)^{a}$ for all $p, a$ , take any $m, n$ and compare prime by prime: writing $m = \prod p^{a_{p}}$ , $n = \prod p^{b_{p}}$ , both $f (mn)$ and $f (m) f (n)$ equal $\prod_{p} f (p)^{a_{p} + b_{p}}$ , using multiplicativity of $f$ across distinct primes. Hence $f (mn) = f (m) f (n)$ with no coprimality hypothesis.∎

Intuition. Reading a Dirichlet series as an Euler product is reading a function "one prime at a time". Every question about a multiplicative function that does not involve how the primes interact — and most do not — becomes a question about a single power series in $p^{- s}$ .

Exercises for §4.6 →

4.7Euler's totient: definition and first values

Definition 4.29 (Euler's totient function). For $n \geq 1$ , Euler's totient $φ (n)$ is the number of integers $k$ with $1 \leq k \leq n$ and $g cd (k, n) = 1$ :

φ (n) = # {k : 1 \leq k \leq n, g cd (k, n) = 1} .

The convention $φ (1) = 1$ falls out of the definition — $k = 1$ is counted, since $g cd (1, 1) = 1$ — and it is the right convention, as every identity below confirms. For a prime $p$ every one of $1, \dots, p - 1$ is coprime to $p$ and $p$ itself is not, so $φ (p) = p - 1$ ; this is the largest $φ (n)$ can be, and it characterises the primes.

Proposition 4.30 (The totient characterises primes). For $n > 1$ : $φ (n) = n - 1$ if and only if $n$ is prime.

Proof. If $n = p$ is prime the count above gives $p - 1$ . Conversely suppose $n > 1$ is composite, say $n = ab$ with $1 < a < n$ . Then $a$ lies in ${1, \dots, n}$ , is not $n$ , and satisfies $g cd (a, n) = a > 1$ , so at least two of the $n$ integers in the range — namely $a$ and $n$ — are excluded from the count, giving $φ (n) \leq n - 2$ .∎

Theorem 4.31 (Totient of a prime power). For a prime $p$ and $a \geq 1$ ,

φ (p^{a}) = p^{a} - p^{a - 1} = p^{a} (1 - \frac{1}{p}) .

Proof. An integer $k$ in ${1, \dots, p^{a}}$ fails to be coprime to $p^{a}$ exactly when $p ∣ k$ , since $p$ is the only prime dividing $p^{a}$ . The multiples of $p$ in that range are $p, 2 p, \dots, p^{a - 1} \cdot p$ , of which there are $p^{a - 1}$ . Subtracting from the total $p^{a}$ gives the formula.∎

Example 4.32 (Small totients). Compute $φ (n)$ for $n = 9, 16, 12, 30$ directly from the definition, and check the prime-power values against the theorem.

Solution.

$φ (9)$ : of $1, \dots, 9$ the multiples of $3$ are $3, 6, 9$ , so $φ (9) = 9 - 3 = 6$ , matching $3^{2} - 3^{1}$ .
$φ (16) = 16 - 8 = 8$ , the excluded numbers being the eight even ones.
$φ (12)$ : coprime residues are $1, 5, 7, 11$ , so $φ (12) = 4$ .
$φ (30)$ : coprime residues are $1, 7, 11, 13, 17, 19, 23, 29$ , so $φ (30) = 8$ .

□

Figure 4.33. Values of

φ (n)

for

n \leq 40

. Every point lies on or below the line

y = n - 1

, touching it exactly at the primes; the points sink toward the bottom of the strip when

n

has many small prime factors, as at

n = 30

Remark. The scatter never settles down. Along the primes $φ (n) / n \to 1$ ; along $n = 2 \cdot 3 \dots p_{r}$ the ratio is $\prod_{p \leq p_{r}} (1 - 1/ p)$ , which tends to $0$ by Mertens' third theorem. So $φ (n) / n$ has every point of $[0, 1]$ as a limit point, and no asymptotic formula for $φ (n)$ itself exists — only for its average, which is $6 x / π^{2}$ per integer.

Exercises for §4.7 →

4.8The product formula, via inclusion–exclusion

There are two proofs of the closed formula for $φ$ , and both are worth having. The first counts directly with inclusion–exclusion and needs no structural theory at all; the second, in the next section, deduces it from multiplicativity in two lines. The first proof is the one that explains why the answer is a product over the distinct primes and does not see the exponents.

Theorem 4.34 (Euler's product formula). For $n \geq 1$ with distinct prime divisors $p_{1}, \dots, p_{r}$ ,

φ (n) = n i = 1 \prod r (1 - \frac{1}{p _{i}}) = i = 1 \prod r (p_{i}^{a_{i}} - p_{i}^{a_{i} - 1}),

where $n = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ .

Proof. By inclusion–exclusion. For each $i$ let $A_{i} = {k : 1 \leq k \leq n, p_{i} ∣ k}$ . An integer $k$ in ${1, \dots, n}$ satisfies $g cd (k, n) > 1$ precisely when some prime dividing $n$ divides $k$ , that is, precisely when $k \in A_{1} \cup \dots \cup A_{r}$ . Hence

φ (n) = n - ∣ A_{1} \cup \dots \cup A_{r} ∣ .

For any subset $S \subseteq {1, \dots, r}$ , the intersection $⋂_{i \in S} A_{i}$ consists of the multiples of $\prod_{i \in S} p_{i}$ in ${1, \dots, n}$ , because the $p_{i}$ are distinct primes so divisibility by each is divisibility by the product. Since $\prod_{i \in S} p_{i}$ divides $n$ , the number of such multiples is exactly $n / \prod_{i \in S} p_{i}$ with no rounding. Inclusion–exclusion gives

φ (n) = S \subseteq {1, \dots, r} \sum (- 1)^{∣ S ∣} \frac{n}{\prod _{i \in S} p _{i}} = n S \sum i \in S \prod (\frac{- 1}{p _{i}}) .

The last sum is the expansion of the product $\prod_{i = 1}^{r} (1 - 1/ p_{i})$ : choosing, from each factor, either the $1$ or the $- 1/ p_{i}$ corresponds exactly to choosing the subset $S$ of indices contributing their second term. Therefore $φ (n) = n \prod_{i} (1 - 1/ p_{i})$ . Distributing $n = \prod p_{i}^{a_{i}}$ one factor at a time turns each $p_{i}^{a_{i}} (1 - 1/ p_{i})$ into $p_{i}^{a_{i}} - p_{i}^{a_{i} - 1}$ , which is the second form.∎

Intuition. Read $φ (n) / n$ as a probability: a random $k$ avoids $p_{1}$ with probability $1 - 1/ p_{1}$ , avoids $p_{2}$ with probability $1 - 1/ p_{2}$ , and — because the $p_{i}$ are distinct primes dividing $n$ — these events are genuinely independent on the range $1$ to $n$ . The formula is the product rule for independent events, and the exactness of $n / \prod_{i \in S} p_{i}$ in the proof is precisely that independence.

Example 4.35 (Computing $φ$ from the factorisation). Compute $φ (600)$ , $φ (1001)$ and $φ (2^{10})$ .

Solution.

$600 = 2^{3} \cdot 3 \cdot 5^{2}$ , so $φ (600) = 600 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 600 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 160$ .
$1001 = 7 \cdot 11 \cdot 13$ , all distinct primes, so $φ (1001) = 6 \cdot 10 \cdot 12 = 720$ .
$φ (2^{10}) = 2^{10} - 2^{9} = 512$ .

□

Corollary 4.36 (Divisibility and parity). $φ (n)$ is even for every $n > 2$ . Moreover if $m ∣ n$ then $φ (m) ∣ φ (n)$ .

Proof. For the parity: if $n$ has an odd prime factor $p$ with $p^{a} ∥ n$ , then the factor $p^{a} - p^{a - 1} = p^{a - 1} (p - 1)$ is even, so the product is. Otherwise $n = 2^{a}$ with $a \geq 2$ , and $φ (n) = 2^{a - 1}$ is even.

For the divisibility, compare prime by prime. Write $m = \prod p^{b_{p}}$ and $n = \prod p^{a_{p}}$ with $b_{p} \leq a_{p}$ . Then $φ (m) = \prod_{b_{p} \geq 1} p^{b_{p} - 1} (p - 1)$ and $φ (n) = \prod_{a_{p} \geq 1} p^{a_{p} - 1} (p - 1)$ . Every prime $p$ with $b_{p} \geq 1$ also has $a_{p} \geq b_{p} \geq 1$ , so each factor $p^{b_{p} - 1} (p - 1)$ of $φ (m)$ divides the corresponding factor $p^{a_{p} - 1} (p - 1)$ of $φ (n)$ , and the remaining factors of $φ (n)$ are integers. Multiplying, $φ (m) ∣ φ (n)$ .∎

Pitfall. The formula sees only the distinct primes in the bracket form, which tempts one to write $φ (p^{a}) = p - 1$ . It is $p^{a} - p^{a - 1}$ : the exponent has been absorbed into the leading $n$ , not discarded. Similarly $φ (mn) = φ (m) φ (n)$ requires $g cd (m, n) = 1$ ; for $m = n = 2$ it gives $1$ instead of the correct $φ (4) = 2$ .

Exercises for §4.8 →

4.9Multiplicativity, Euler's theorem, and the second proof

The totient is multiplicative, and the cleanest proof is structural: $φ (n)$ counts the units of $Z / n Z$ , and the Chinese remainder theorem splits that unit group across coprime factors.

Theorem 4.37 ( $φ$ counts units). For $n \geq 1$ , the residue class of $k$ is invertible in the ring $Z / n Z$ if and only if $g cd (k, n) = 1$ . Hence $∣ (Z / n Z)^{\times} ∣ = φ (n)$ .

Proof. If $g cd (k, n) = 1$ , Bézout gives integers $x, y$ with $k x + n y = 1$ , so $k x \equiv 1 (mod n)$ and $k$ is invertible. Conversely if $k x \equiv 1 (mod n)$ then $k x - 1 = n y$ for some $y$ , so any common divisor of $k$ and $n$ divides $1$ , forcing $g cd (k, n) = 1$ . The residues $1, \dots, n$ represent each class of $Z / n Z$ exactly once, so counting invertible classes counts exactly the $k$ in that range with $g cd (k, n) = 1$ .∎

Theorem 4.38 ( $φ$ is multiplicative). If $g cd (m, n) = 1$ then $φ (mn) = φ (m) φ (n)$ .

Proof. The Chinese remainder theorem gives a ring isomorphism

Z / mn Z ≅ Z / m Z \times Z / n Z, k mod mn ⟼ (k mod m, k mod n),

valid because $g cd (m, n) = 1$ . A ring isomorphism carries units to units, and a pair is a unit in a product ring exactly when each coordinate is. Hence

(Z / mn Z)^{\times} = (Z / m Z)^{\times} \cdot (Z / n Z)^{\times},

which by $φ$ counts units is $φ (mn) = φ (m) φ (n)$ . Since $φ (1) = 1$ , $φ$ is multiplicative.∎

Corollary 4.39 (Euler's product formula, second proof).

φ (n) = i \prod (p_{i}^{a_{i}} - p_{i}^{a_{i} - 1})

Proof. By $φ$ is multiplicative and A multiplicative function is determined by its prime powers, $φ (n) = \prod_{i} φ (p_{i}^{a_{i}})$ , and each factor is $p_{i}^{a_{i}} - p_{i}^{a_{i} - 1}$ by Totient of a prime power.∎

Comparing the two proofs is instructive. The inclusion–exclusion argument is self-contained and gives the answer for a single $n$ with no theory; the structural argument gives the answer for all $n$ at once and explains the product as a decomposition of a group. Both take about a page; only the second generalises, and it is the one that tells us what $φ (n)$ is rather than merely how large it is.

Theorem 4.40 (Euler's theorem). If $g cd (a, n) = 1$ then

a^{φ (n)} \equiv 1 (mod n) .

Proof. The group $G = (Z / n Z)^{\times}$ is finite of order $φ (n)$ by $φ$ counts units, and $a$ represents an element of $G$ . By Lagrange's theorem the order of the cyclic subgroup generated by $a$ divides $∣ G ∣ = φ (n)$ , so $a^{φ (n)}$ is the identity of $G$ , which is the class of $1$ .

Without group theory the same argument runs directly: let $r_{1}, \dots, r_{φ (n)}$ be the residues coprime to $n$ . Multiplication by $a$ permutes them, since $a r_{i}$ is again coprime to $n$ and $a r_{i} \equiv a r_{j}$ forces $r_{i} \equiv r_{j}$ after cancelling the invertible $a$ . Taking the product of all of them, $\prod_{i} (a r_{i}) \equiv \prod_{i} r_{i}$ , that is $a^{φ (n)} \prod_{i} r_{i} \equiv \prod_{i} r_{i} (mod n)$ ; the product $\prod r_{i}$ is coprime to $n$ and hence cancellable, leaving $a^{φ (n)} \equiv 1$ .∎

Corollary 4.41 (Fermat's little theorem). If $p$ is prime and $p ∤ a$ then $a^{p - 1} \equiv 1 (mod p)$ .

Proof. Take $n = p$ in Euler's theorem and use $φ (p) = p - 1$ .∎

Example 4.42 (Reducing a large power). Compute $7^{2024} mod 45$ .

Solution.

$45 = 3^{2} \cdot 5$ , so $φ (45) = (9 - 3) (5 - 1) = 24$ , and $g cd (7, 45) = 1$ .
By Euler's theorem, $7^{24} \equiv 1 (mod 45)$ .
$2024 = 24 \cdot 84 + 8$ , so $7^{2024} \equiv 7^{8} (mod 45)$ .
$7^{2} = 49 \equiv 4$ ; $7^{4} \equiv 4^{2} = 16$ ; $7^{8} \equiv 1 6^{2} = 256 \equiv 256 - 225 = 31 (mod 45)$ .
Final value: $31$ .

□

Exercises for §4.9 →

4.10Divisor sums of the totient

One identity dominates the applications of $φ$ , and it is the first genuinely non-obvious convolution identity in the chapter.

Theorem 4.43 (Gauss's divisor sum for $φ$ ). For every $n \geq 1$ ,

d ∣ n \sum φ (d) = n, equivalently φ * u = id .

Proof. By partitioning the fractions. Consider the $n$ fractions $\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$ and reduce each to lowest terms. Each reduced fraction has the form $a / d$ with $d ∣ n$ , $1 \leq a \leq d$ and $g cd (a, d) = 1$ ; conversely every such $a / d$ arises exactly once, from $k = a \cdot (n / d)$ . So the $n$ fractions are partitioned by their reduced denominator $d$ , and the class with denominator $d$ has exactly $φ (d)$ members. Counting the whole set in two ways gives $n = \sum_{d ∣ n} φ (d)$ .

By multiplicativity. Alternatively, $φ * u$ is multiplicative by Convolution preserves multiplicativity, so it suffices to check it at prime powers. By Local factors of a convolution,

(φ * u) (p^{a}) = j = 0 \sum a φ (p^{j}) = 1 + j = 1 \sum a (p^{j} - p^{j - 1}) = p^{a},

the sum telescoping. Since $id$ is also multiplicative and agrees at every prime power, the two functions are equal.∎

Remark. The two proofs are not the same argument in different clothes. The first is a bijection and gives the result for one $n$ without knowing $φ$ is multiplicative; the second is a telescoping sum and needs the theory. Given Möbius inversion, later in the chapter, this identity will be run backwards to recover $φ = μ * id$ , which is how $φ$ is usually computed in the convolution ring.

Example 4.44 (Checking Gauss's identity). Verify $\sum_{d ∣ 18} φ (d) = 18$ .

Solution.

Divisors of $18$ : $1, 2, 3, 6, 9, 18$ .
Totients: $φ (1) = 1$ , $φ (2) = 1$ , $φ (3) = 2$ , $φ (6) = 2$ , $φ (9) = 6$ , $φ (18) = 6$ .
Sum: $1 + 1 + 2 + 2 + 6 + 6 = 18$ .

□

Proposition 4.45 (Sum of the coprime residues). For $n > 1$ ,

1 \leq k \leq n g c d (k, n) = 1 \sum k = \frac{n φ ( n )}{2} .

Proof. Pair $k$ with $n - k$ . Since $g cd (k, n) = g cd (n - k, n)$ , the map $k \mapsto n - k$ is an involution of the set $C$ of residues coprime to $n$ in ${1, \dots, n - 1}$ — note $k = n$ is excluded as $n > 1$ means $g cd (n, n) = n > 1$ . It has no fixed point: $k = n - k$ would give $n = 2 k$ , so $g cd (k, n) = k$ , which is $1$ only if $n = 2$ , and for $n = 2$ the set $C = {1}$ has odd size with $1 = 2 - 1$ its own partner, giving the sum $1 = 2 \cdot 1/2$ as claimed. For $n > 2$ , $C$ splits into $φ (n) /2$ pairs each summing to $n$ , so the total is $n φ (n) /2$ .∎

Example 4.46 (A totient equation). Find all $n$ with $φ (n) = 8$ .

Solution.

Write $n = \prod p_{i}^{a_{i}}$ ; then $φ (n) = \prod p_{i}^{a_{i} - 1} (p_{i} - 1) = 8$ , so every $p_{i} - 1$ divides $8$ and every odd $p_{i}$ contributes $p_{i}^{a_{i} - 1}$ as a divisor of $8$ , forcing $a_{i} = 1$ for odd $p_{i}$ .
Odd primes with $p - 1 ∣ 8$ : $p \in {3, 5}$ give $p - 1 = 2, 4$ . ( $p = 9$ is not prime; $p - 1 = 8$ gives $p = 9$ , excluded.)
The power of $2$ contributes $1$ if $a = 0$ or $1$ , and $2^{a - 1}$ if $a \geq 1$ .
Enumerating: $n = 15$ ( $2 \cdot 4 = 8$ ), $n = 16$ ( $2^{3} = 8$ ), $n = 20 = 2^{2} \cdot 5$ ( $2 \cdot 4$ ), $n = 24 = 2^{3} \cdot 3$ ( $4 \cdot 2$ ), $n = 30 = 2 \cdot 3 \cdot 5$ ( $1 \cdot 2 \cdot 4$ ).
So the solution set is ${15, 16, 20, 24, 30}$ , five values — the totient is far from injective.

□

Exercises for §4.10 →

4.11The Möbius function

The Möbius function exists to invert divisor sums. Its definition looks arbitrary — three cases, one of which is a sign — and the only honest motivation is the identity proved at the end of this section, which is what the definition was reverse-engineered to satisfy.

Definition 4.47 (Möbius function). For $n \geq 1$ ,

μ (n) = ⎩ ⎨ ⎧ 1 (- 1)^{r} 0 n = 1, n = p_{1} p_{2} \dots p_{r} with the p_{i} distinct primes, n is divisible by p^{2} for some prime p .

Equivalently, $μ (n) = (- 1)^{ω (n)}$ if $n$ is squarefree and $0$ otherwise.

So $μ$ is supported on the squarefree integers and records the parity of the number of prime factors there. The first values are $μ (1) = 1$ , $μ (2) = μ (3) = - 1$ , $μ (4) = 0$ , $μ (5) = - 1$ , $μ (6) = 1$ , $μ (7) = - 1$ , $μ (8) = μ (9) = 0$ , $μ (10) = 1$ .

Figure 4.48. The Möbius function on

1 \leq n \leq 20

. It takes only the values

+ 1

- 1

and

0

; a bar is missing exactly at the non-squarefree

n

, and the sign of the rest is the parity of the number of prime factors.

Proposition 4.49 ( $μ$ is multiplicative). $μ$ is multiplicative: $μ (1) = 1$ and $μ (mn) = μ (m) μ (n)$ whenever $g cd (m, n) = 1$ . It is not completely multiplicative.

Proof. Let $g cd (m, n) = 1$ . If either $m$ or $n$ is divisible by a square $p^{2}$ , then so is $mn$ , and both sides are $0$ . Otherwise both are squarefree; since they share no prime, $mn$ is squarefree too, and its distinct primes are those of $m$ together with those of $n$ , with no overlap. Hence $ω (mn) = ω (m) + ω (n)$ and

μ (mn) = (- 1)^{ω (m) + ω (n)} = (- 1)^{ω (m)} (- 1)^{ω (n)} = μ (m) μ (n) .

It is not completely multiplicative because $μ (4) = 0$ while $μ (2)^{2} = 1$ .∎

Remark. On prime powers $μ$ is as simple as a function can be: $μ (p) = - 1$ , and $μ (p^{a}) = 0$ for every $a \geq 2$ . Combined with A multiplicative function is determined by its prime powers this is an alternative definition, and it is the one to use in a proof, since it turns any local factor $\sum_{j = 0}^{a} μ (p^{j}) f (p^{a - j})$ into a two-term expression.

Theorem 4.50 (The Möbius sum identity). For every $n \geq 1$ ,

d ∣ n \sum μ (d) = {10 n = 1, n > 1,

that is, $μ * u = ε$ .

Proof. For $n = 1$ the only divisor is $1$ and $μ (1) = 1$ .

For $n > 1$ , let $p_{1}, \dots, p_{r}$ be the distinct primes dividing $n$ , so $r \geq 1$ . A divisor $d$ of $n$ contributes nothing unless it is squarefree, so only the $2^{r}$ divisors $d = \prod_{i \in S} p_{i}$ for $S \subseteq {1, \dots, r}$ matter, and such a $d$ contributes $(- 1)^{∣ S ∣}$ . Grouping the subsets by size,

d ∣ n \sum μ (d) = k = 0 \sum r (k r) (- 1)^{k} = (1 - 1)^{r} = 0,

by the binomial theorem, using $r \geq 1$ so that $0^{r} = 0$ .

Alternatively and more briefly: $μ * u$ is multiplicative by Convolution preserves multiplicativity, and at a prime power $(μ * u) (p^{a}) = μ (1) + μ (p) + 0 + \dots + 0 = 1 - 1 = 0$ for $a \geq 1$ , which is $ε (p^{a})$ .∎

Intuition. The identity is inclusion–exclusion in disguise, and the disguise is thin: the alternating sum $\sum_{k} (k r) (- 1)^{k}$ is exactly the signed count that appears when one over-counts a union and corrects. This is why $μ$ shows up wherever a counting problem is solved by sieving.

Exercises for §4.11 →

4.12Möbius inversion

Möbius inversion is the statement that convolving with $u$ is an invertible operation, whose inverse is convolving with $μ$ . Once The Möbius sum identity is available and convolution is known to be associative, the proof is two lines; the content is entirely in that identity.

Theorem 4.51 (Möbius inversion). Let $f$ and $g$ be arithmetic functions. Then

g (n) = d ∣ n \sum f (d) for all n ⟺ f (n) = d ∣ n \sum μ (d) g (n / d) for all n .

In convolution notation. $g = f * u$ if and only if $f = μ * g$ .

Proof. ( $\Rightarrow$ ) Suppose $g = f * u$ . Convolve with $μ$ and use commutativity and associativity, established in Convolution makes a commutative ring:

μ * g = μ * (f * u) = f * (μ * u) = f * ε = f,

the third equality by The Möbius sum identity and the fourth because $ε$ is the convolution identity.

( $\Leftarrow$ ) Suppose $f = μ * g$ . Then

f * u = (μ * g) * u = g * (μ * u) = g * ε = g,

by the same three facts. So each statement implies the other.∎

Remark. The symmetry of the two directions is not an accident of the proof; it is the statement that $u$ is a unit of the Dirichlet ring with inverse $μ$ . Every "inversion formula" in combinatorics is of this shape — an incidence algebra in which one element is invertible — and the Möbius function of the divisibility order is the prototype.

Example 4.52 (Recovering $φ$ by inversion). Apply Möbius inversion to Gauss's identity $\sum_{d ∣ n} φ (d) = n$ .

Solution.

The identity says $id = φ * u$ , so the hypothesis of Möbius inversion holds with $f = φ$ , $g = id$ .
Inverting, $φ = μ * id$ , that is $φ (n) = \sum_{d ∣ n} μ (d) \frac{n}{d}$ .
Check at $n = 12$ : the squarefree divisors are $1, 2, 3, 6$ with $μ$ -values $1, - 1, - 1, 1$ , giving $12 - 6 - 4 + 2 = 4 = φ (12)$ .
Dividing by $n$ turns the formula into $φ (n) / n = \sum_{d ∣ n} μ (d) / d$ , which on expanding over the squarefree divisors is exactly Euler's product $\prod_{p ∣ n} (1 - 1/ p)$ — a third proof of Euler's product formula.

□

Corollary 4.53 (Multiplicativity transfers through inversion). If $g = f * u$ then $f$ is multiplicative if and only if $g$ is.

Proof. If $f$ is multiplicative then so is $g = f * u$ by Convolution preserves multiplicativity, since $u$ is multiplicative. Conversely if $g$ is multiplicative then $f = μ * g$ is multiplicative by the same theorem, since $μ$ is multiplicative by $μ$ is multiplicative.∎

Example 4.54 (Inverting the divisor count). Given that $d = u * u$ , find the function $f$ with $f * u = d$ , and verify at $n = 12$ .

Solution.

By Möbius inversion, $f = μ * d$ . But $d = u * u$ , so $f = μ * u * u = ε * u = u$ .
So $f = u$ , which is the identity $\sum_{d ∣ n} 1 = d (n)$ we started from — consistent.
At $n = 12$ : $\sum_{d ∣ 12} μ (d) d (12/ d) = μ (1) d (12) + μ (2) d (6) + μ (3) d (4) + μ (4) d (3) + μ (6) d (2) + μ (12) d (1)$ .
This is $6 - 4 - 3 + 0 + 2 + 0 = 1 = u (12)$ .

□

Pitfall. Möbius inversion requires the relation to hold for every $n$ , not just the one of interest; the inverse formula at $n$ uses $g$ at all divisors of $n$ . And the $μ$ and the argument must be paired as $μ (d) g (n / d)$ — writing $μ (n / d) g (d)$ gives the same sum by symmetry of the divisor pairing, but $μ (d) g (d)$ gives nonsense.

Exercises for §4.12 →

4.13The sum identity and what it does

The identity $μ * u = ε$ deserves a section of its own because almost every use of $μ$ in practice is an application of it in the following form: it is a detector for the condition $n = 1$ , and can be inserted into any sum to impose a coprimality or exactness constraint.

Proposition 4.55 ( $μ$ as an indicator). For positive integers $a, b$ ,

d ∣ g c d (a, b) \sum μ (d) = {10 g cd (a, b) = 1, otherwise.

Proof. Apply The Möbius sum identity with $n = g cd (a, b)$ : the sum is $ε (g cd (a, b))$ , which is $1$ exactly when $g cd (a, b) = 1$ .∎

That single proposition converts "count the $k$ coprime to $n$ " into a double sum with no coprimality condition, which can then be exchanged. It is the engine behind the sieve of Eratosthenes made quantitative.

Example 4.56 (Euler's formula by sieving). Use $μ$ as an indicator to recompute $φ (n)$ .

Solution.

$φ (n) = \sum_{k = 1}^{n} ε (g cd (k, n)) = \sum_{k = 1}^{n} \sum_{d ∣ g c d (k, n)} μ (d)$ .
Exchange the order: $d$ ranges over divisors of $n$ , and for fixed $d$ the inner condition $d ∣ k$ , $1 \leq k \leq n$ has exactly $n / d$ solutions.
So $φ (n) = \sum_{d ∣ n} μ (d) \frac{n}{d}$ , which is $φ = μ * id$ again.
Expanding over squarefree divisors gives $n \prod_{p ∣ n} (1 - 1/ p)$ .

□

Definition 4.57 (Mertens function). The Mertens function is the summatory function of $μ$ :

M (x) = n \leq x \sum μ (n) .

The pointwise identity $\sum_{d ∣ n} μ (d) = 0$ says the signs cancel within each $n > 1$ ; the size of $M (x)$ asks whether they cancel across $n$ , which is a far deeper question. $M (x) = O (x^{1/2 + ε})$ is equivalent to the Riemann hypothesis, and even $M (x) = o (x)$ is equivalent to the prime number theorem.

Proposition 4.58 (A crude bound on $M$ ). $∣ M (x) ∣ \leq x$ for all $x \geq 1$ , and $M$ takes the values $M (1) = 1$ , $M (2) = 0$ , $M (3) = - 1$ , $M (4) = - 1$ , $M (10) = - 1$ , $M (100) = 1$ .

Proof. The bound is the triangle inequality: $∣ M (x) ∣ \leq \sum_{n \leq x} ∣ μ (n) ∣ \leq ⌊ x ⌋ \leq x$ , since $∣ μ (n) ∣ \leq 1$ . The listed values are direct summation of the table of $μ$ given after the definition, extended by the same rule.∎

Proposition 4.59 (Squarefree indicator). For every $n \geq 1$ ,

μ^{2} (n) = d^{2} ∣ n \sum μ (d),

which is $1$ if $n$ is squarefree and $0$ otherwise.

Proof. Both sides are multiplicative: the left by $μ$ is multiplicative and Products and quotients; the right because $\sum_{d^{2} ∣ n} μ (d)$ is the convolution-type sum whose value at $n$ depends only on the exponents, and splitting $n$ into coprime parts splits the condition $d^{2} ∣ n$ as $d = d_{1} d_{2}$ with $d_{i}^{2}$ dividing the respective part, exactly as in Divisors of a coprime product. So check at $p^{a}$ : the $d$ with $d^{2} ∣ p^{a}$ are $d = p^{j}$ with $2 j \leq a$ , and $μ (p^{j}) = 0$ unless $j \in {0, 1}$ . For $a = 0$ or $a = 1$ only $j = 0$ qualifies, giving $1$ ; for $a \geq 2$ both $j = 0$ and $j = 1$ qualify, giving $1 - 1 = 0$ . That is exactly $μ^{2} (p^{a})$ .∎

Example 4.60 (Counting squarefree integers up to $x$ ). Use Squarefree indicator to estimate the number of squarefree integers not exceeding $x$ .

Solution.

$Q (x) = \sum_{n \leq x} μ^{2} (n) = \sum_{n \leq x} \sum_{d^{2} ∣ n} μ (d)$ .
Exchange: for each $d \leq x$ the number of $n \leq x$ with $d^{2} ∣ n$ is $⌊ x / d^{2} ⌋$ , so $Q (x) = \sum_{d \leq x} μ (d) ⌊ x / d^{2} ⌋$ .
Replace the floor by $x / d^{2} + O (1)$ ; the errors total $O (x)$ .
The main term is $x \sum_{d \leq x} μ (d) / d^{2} = x (1/ ζ (2) + O (1/ x))$ .
Hence $Q (x) = 6 x / π^{2} + O (x)$ , agreeing with the density found in Counting squarefree integers.

□

Exercises for §4.13 →

4.14Applications of Möbius inversion

Möbius inversion is used whenever a quantity is easy to compute "with multiplicity" and hard to compute exactly. Two standard examples follow, one from polynomial algebra and one from combinatorics on words; both have the same shape, a total that decomposes over divisors.

Theorem 4.61 (Counting monic irreducibles over a finite field). Let $q$ be a prime power and let $N_{q} (n)$ be the number of monic irreducible polynomials of degree $n$ over $F_{q}$ . Then

d ∣ n \sum d N_{q} (d) = q^{n}, hence N_{q} (n) = \frac{1}{n} d ∣ n \sum μ (d) q^{n / d} .

Proof. The field $F_{q^{n}}$ is the splitting field of $x^{q^{n}} - x$ over $F_{q}$ , and that polynomial is squarefree since its derivative is $- 1$ . Its monic irreducible factors over $F_{q}$ are exactly the monic irreducibles whose degree divides $n$ : an irreducible of degree $d$ has its roots in $F_{q^{d}}$ , which sits inside $F_{q^{n}}$ precisely when $d ∣ n$ . Comparing degrees on both sides of the factorisation of $x^{q^{n}} - x$ gives $\sum_{d ∣ n} d N_{q} (d) = q^{n}$ .

Now set $f (d) = d N_{q} (d)$ and $g (n) = q^{n}$ . The displayed identity is $g = f * u$ , so Möbius inversion gives $f (n) = \sum_{d ∣ n} μ (d) q^{n / d}$ ; dividing by $n$ gives the formula.∎

Example 4.62 (Irreducible cubics and quartics over $F_{2}$ ). Compute $N_{2} (3)$ and $N_{2} (4)$ .

Solution.

$N_{2} (3) = \frac{1}{3} (μ (1) 2^{3} + μ (3) 2^{1}) = \frac{1}{3} (8 - 2) = 2$ . The two are $x^{3} + x + 1$ and $x^{3} + x^{2} + 1$ .
$N_{2} (4) = \frac{1}{4} (μ (1) 2^{4} + μ (2) 2^{2} + μ (4) 2^{1}) = \frac{1}{4} (16 - 4 + 0) = 3$ .
As a sanity check, $N_{2} (1) = 2$ (namely $x$ and $x + 1$ ) and $1 \cdot 2 + 2 \cdot N_{2} (2) = 4$ gives $N_{2} (2) = 1$ , the polynomial $x^{2} + x + 1$ .

□

Proposition 4.63 (Necklace counting). The number of aperiodic binary strings of length $n$ , up to nothing (as linear strings), is $\sum_{d ∣ n} μ (d) 2^{n / d}$ , and the number of binary necklaces with primitive period $n$ is $\frac{1}{n} \sum_{d ∣ n} μ (d) 2^{n / d}$ .

Proof. Every binary string of length $n$ has a unique primitive period $d ∣ n$ , namely the least $d$ such that the string is a $d$ -block repeated $n / d$ times. Letting $A (d)$ be the number of strings of length $d$ that are aperiodic, classifying the $2^{n}$ strings by their primitive period gives $\sum_{d ∣ n} A (d) = 2^{n}$ . By Möbius inversion, $A (n) = \sum_{d ∣ n} μ (d) 2^{n / d}$ . Cyclic rotation acts freely on the aperiodic strings of length $n$ — a nontrivial rotation fixing a string would force a smaller period — so the orbits all have size $n$ and there are $A (n) / n$ of them.∎

Remark. The identical shape of the last two results is not coincidence: $N_{q} (n)$ counts orbits of the Frobenius map on $F_{q^{n}}$ , and the Frobenius is a cyclic rotation of the "string" of conjugates. The necklace formula and the irreducible-polynomial formula are the same theorem about a cyclic group acting freely.

Exercises for §4.14 →

4.15Divisor functions

Definition 4.64 (Divisor-power functions). For $k \geq 0$ and $n \geq 1$ ,

σ_{k} (n) = d ∣ n \sum d^{k} .

In particular $σ_{0} = d$ counts the divisors and $σ_{1} = σ$ sums them. When $k$ is omitted, $σ$ means $σ_{1}$ .

Theorem 4.65 (Divisor-power sums as a convolution). $σ_{k} = id_{k} * u$ , and consequently $σ_{k}$ is multiplicative for every $k \geq 0$ .

Proof. By definition $(id_{k} * u) (n) = \sum_{d ∣ n} d^{k} \cdot 1 = σ_{k} (n)$ . Both $id_{k}$ and $u$ are completely multiplicative, hence multiplicative, so Convolution preserves multiplicativity makes $σ_{k}$ multiplicative.∎

Example 4.66 (Divisor counts and sums). Compute $d (720)$ , $σ (720)$ and $σ_{2} (12)$ .

Solution.

$720 = 2^{4} \cdot 3^{2} \cdot 5$ , so $d (720) = 5 \cdot 3 \cdot 2 = 30$ .
$σ (720) = (2^{5} - 1) \cdot \frac{3 ^{3} - 1}{2} \cdot \frac{5 ^{2} - 1}{4} = 31 \cdot 13 \cdot 6 = 2418$ .
$12 = 2^{2} \cdot 3$ , so $σ_{2} (12) = (1 + 4 + 16) (1 + 9) = 21 \cdot 10 = 210$ ; directly, $1 + 4 + 9 + 16 + 36 + 144 = 210$ .

□

Proposition 4.67 (Divisors come in pairs). The map $e \mapsto n / e$ is an involution on the divisors of $n$ , and

σ_{k} (n) = n^{k} σ_{- k} (n) = n^{k} d ∣ n \sum d^{- k} .

Consequently $d (n)$ is odd if and only if $n$ is a perfect square.

Proof. If $e ∣ n$ then $n / e ∣ n$ , and applying the map twice returns $e$ , so it is an involution and in particular a bijection of the divisor set. Substituting $d = n / e$ in the defining sum gives $σ_{k} (n) = \sum_{e ∣ n} (n / e)^{k} = n^{k} \sum_{e ∣ n} e^{- k}$ .

For the parity of $d (n)$ : the involution pairs up divisors, so $d (n)$ is odd exactly when the involution has a fixed point, that is when $e = n / e$ for some divisor, i.e. $n = e^{2}$ . (A fixed point is unique when it exists, since $e$ is determined as $n$ .)∎

Example 4.68 (A divisor-count equation). Find the smallest positive integer with exactly $12$ divisors.

Solution.

If $n = \prod p_{i}^{a_{i}}$ then $d (n) = \prod (a_{i} + 1)$ , so the exponent pattern must have $\prod (a_{i} + 1) = 12$ .
The factorisations of $12$ into factors $\geq 2$ are $12$ , $6 \cdot 2$ , $4 \cdot 3$ , $3 \cdot 2 \cdot 2$ , $2 \cdot 6$ , and so on; the exponent multisets are ${11}$ , ${5, 1}$ , ${3, 2}$ , ${2, 1, 1}$ .
To minimise $n$ , assign the largest exponent to the smallest prime: $2^{11} = 2048$ ; $2^{5} \cdot 3 = 96$ ; $2^{3} \cdot 3^{2} = 72$ ; $2^{2} \cdot 3 \cdot 5 = 60$ .
The smallest is $60$ , with divisors $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ .

□

Pitfall. $σ$ is multiplicative, not additive or completely multiplicative. $σ (4) = 7$ while $σ (2)^{2} = 9$ ; and $σ (2 + 3) = σ (5) = 6$ has no relation to $σ (2) + σ (3) = 7$ . Only coprime products split.

Exercises for §4.15 →

4.16Formulas and Dirichlet series for $σ_{k}$

Theorem 4.69 (Closed formula for $σ_{k}$ ). Let $n = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ . For $k \geq 1$ ,

σ_{k} (n) = i = 1 \prod r \frac{p _{i}^{k (a_{i} + 1)} - 1}{p _{i}^{k} - 1},

and for $k = 0$ ,

d (n) = i = 1 \prod r (a_{i} + 1) .

Proof. By Divisor-power sums as a convolution, $σ_{k}$ is multiplicative, so by A multiplicative function is determined by its prime powers it is enough to evaluate at $p^{a}$ . The divisors of $p^{a}$ are $1, p, \dots, p^{a}$ , so

σ_{k} (p^{a}) = j = 0 \sum a p^{jk} = j = 0 \sum a (p^{k})^{j} .

For $k \geq 1$ this is a geometric series with ratio $p^{k} \neq = 1$ , summing to $(p^{k (a + 1)} - 1) / (p^{k} - 1)$ . For $k = 0$ every term is $1$ and there are $a + 1$ of them. Taking the product over $i$ gives both statements.∎

Corollary 4.70 (Divisor series). For $Re (s) > max (1, k + 1)$ ,

n \geq 1 \sum \frac{σ _{k} ( n )}{n ^{s}} = ζ (s) ζ (s - k) .

Proof. This is The series of $μ$ , $d$ and $σ_{k}$ , restated; it follows from $σ_{k} = id_{k} * u$ and Dirichlet series multiply by convolution.∎

Example 4.71 (Using the closed formula). Compute $σ_{3} (10)$ two ways.

Solution.

Directly: the divisors of $10$ are $1, 2, 5, 10$ , so $σ_{3} (10) = 1 + 8 + 125 + 1000 = 1134$ .
By the formula: $σ_{3} (10) = \frac{2 ^{6} - 1}{2 ^{3} - 1} \cdot \frac{5 ^{6} - 1}{5 ^{3} - 1} = \frac{63}{7} \cdot \frac{15624}{124} = 9 \cdot 126 = 1134$ .

□

Proposition 4.72 (Bounds on $σ$ ). For every $n \geq 1$ ,

n < σ (n) \leq n d (n) (n > 1), \frac{σ ( n )}{n} = d ∣ n \sum \frac{1}{d} < p ∣ n \prod (1 - \frac{1}{p})^{- 1} .

Proof. The lower bound holds because $1$ and $n$ are distinct divisors when $n > 1$ , so $σ (n) \geq n + 1 > n$ . The upper bound $σ (n) = \sum_{d ∣ n} d \leq \sum_{d ∣ n} n = n d (n)$ is term by term.

For the last claim, Divisors come in pairs gives $σ (n) / n = \sum_{d ∣ n} 1/ d$ . Every divisor $d$ of $n$ is a product $\prod p^{c_{p}}$ with $c_{p} \leq a_{p}$ , so $\sum_{d ∣ n} 1/ d = \prod_{p ∣ n} (1 + p^{- 1} + \dots + p^{- a_{p}})$ , and each factor is a truncation of the geometric series $(1 - 1/ p)^{- 1}$ , hence strictly smaller.∎

Remark. Combined with Euler's product formula, the last bound says $σ (n) φ (n) < n^{2}$ for all $n > 1$ : the totient and the divisor sum pull in opposite directions, and their product is pinned near $n^{2}$ . Indeed $σ (n) φ (n) > n^{2} \prod_{p ∣ n} (1 - p^{- 2})$ , so the ratio $σ (n) φ (n) / n^{2}$ lies between $6/ π^{2}$ and $1$ .

Exercises for §4.16 →

4.17Perfect numbers and the Euclid–Euler theorem

Definition 4.73 (Perfect, abundant, deficient). Call $n$ perfect if $σ (n) = 2 n$ , abundant if $σ (n) > 2 n$ , and deficient if $σ (n) < 2 n$ . Equivalently, the sum of the proper divisors $s (n) = σ (n) - n$ equals, exceeds, or falls short of $n$ .

The first perfect numbers are $6 = 1 + 2 + 3$ , $28 = 1 + 2 + 4 + 7 + 14$ , $496$ and $8128$ . Each is of the form $2^{p - 1} (2^{p} - 1)$ with $2^{p} - 1$ prime, and the theorem below says the even ones are exactly these — a complete classification, proved in full, with the odd case still open after twenty-three centuries.

Figure 4.74. The ratio

σ (n) / n

for

n \leq 40

. Deficient numbers sit below the line

σ (n) / n = 2

, abundant numbers above it, and the perfect numbers

6

and

28

land exactly on it. Primes cluster just above

1

, since

σ (p) / p = 1 + 1/ p

Theorem 4.75 (Euclid–Euler). An even number $n$ is perfect if and only if

n = 2^{p - 1} (2^{p} - 1)

for some prime $p$ such that $2^{p} - 1$ is also prime (a Mersenne prime).

Proof. ( $\Leftarrow$ , Euclid.) Let $q = 2^{p} - 1$ be prime and $n = 2^{p - 1} q$ . Since $q$ is odd, $g cd (2^{p - 1}, q) = 1$ , so multiplicativity of $σ$ gives

σ (n) = σ (2^{p - 1}) σ (q) = (2^{p} - 1) (q + 1) = q \cdot 2^{p} = 2 \cdot 2^{p - 1} q = 2 n .

( $\Rightarrow$ , Euler.) Let $n$ be even and perfect. Write $n = 2^{m} q$ with $m \geq 1$ and $q$ odd. Coprimality of $2^{m}$ and $q$ gives

2 n = 2^{m + 1} q = σ (n) = σ (2^{m}) σ (q) = (2^{m + 1} - 1) σ (q) .

Thus $(2^{m + 1} - 1) ∣ 2^{m + 1} q$ , and since $2^{m + 1} - 1$ is odd it divides $q$ ; write $q = (2^{m + 1} - 1) c$ . Substituting,

2^{m + 1} (2^{m + 1} - 1) c = (2^{m + 1} - 1) σ (q), so σ (q) = 2^{m + 1} c = q + c .

Now $c$ and $q$ are both divisors of $q$ — indeed $c = q / (2^{m + 1} - 1)$ — and they are distinct because $m \geq 1$ forces $2^{m + 1} - 1 \geq 3 > 1$ . So $σ (q) \geq q + c$ with equality only if $q$ and $c$ are the only divisors of $q$ . Equality holds, so $q$ has exactly two divisors, forcing $c = 1$ and $q$ prime. Then $q = 2^{m + 1} - 1$ and $n = 2^{m} (2^{m + 1} - 1)$ .

It remains to see that $m + 1$ is prime. If $m + 1 = ab$ with $1 < a < m + 1$ , then $2^{a} - 1$ is a proper divisor of $2^{m + 1} - 1$ strictly greater than $1$ , by the factorisation $2^{ab} - 1 = (2^{a} - 1) (2^{a (b - 1)} + \dots + 1)$ , contradicting primality of $q$ . Setting $p = m + 1$ gives the stated form.∎

Remark. The theorem is a classification only of the even perfect numbers. Whether an odd perfect number exists is open; it is known that one would have to exceed $1 0^{1500}$ , have at least ten distinct prime factors, and satisfy a long list of further constraints, every one of which is derived from the multiplicativity of $σ$ in essentially the manner above.

Example 4.76 (Testing for perfection). Determine whether $496$ and $945$ are perfect, abundant or deficient.

Solution.

$496 = 2^{4} \cdot 31$ and $31 = 2^{5} - 1$ is prime, so Euclid–Euler applies with $p = 5$ : $496$ is perfect. Check: $σ (496) = 31 \cdot 32 = 992 = 2 \cdot 496$ .
$945 = 3^{3} \cdot 5 \cdot 7$ , so $σ (945) = 40 \cdot 6 \cdot 8 = 1920 > 1890 = 2 \cdot 945$ .
So $945$ is abundant — and it is the smallest odd abundant number, which is why abundance is so strongly associated with even numbers.

□

Definition 4.77 (Aliquot sequence, amicable pairs). The aliquot sequence of $n$ is $n, s (n), s (s (n)), \dots$ where $s (n) = σ (n) - n$ . A pair $(m, n)$ with $s (m) = n$ and $s (n) = m$ , $m \neq = n$ , is an amicable pair; a cycle of length $k$ is a sociable chain.

Example 4.78 (The amicable pair $220$ and $284$ ). Verify that $220$ and $284$ are amicable.

Solution.

$220 = 2^{2} \cdot 5 \cdot 11$ , so $σ (220) = 7 \cdot 6 \cdot 12 = 504$ and $s (220) = 504 - 220 = 284$ .
$284 = 2^{2} \cdot 71$ , so $σ (284) = 7 \cdot 72 = 504$ and $s (284) = 504 - 284 = 220$ .
Each is the sum of the other's proper divisors, and note the coincidence that both have $σ = 504$ — which is forced, since $σ (m) = m + n = σ (n)$ for any amicable pair.

□

Exercises for §4.17 →

4.18The Carmichael function

Euler's theorem says $a^{φ (n)} \equiv 1$ for every $a$ coprime to $n$ . It does not say $φ (n)$ is the smallest exponent that works, and usually it is not: modulo $8$ every odd $a$ satisfies $a^{2} \equiv 1$ , while $φ (8) = 4$ . The sharp exponent has a name and a formula.

Definition 4.79 (Carmichael function). For $n \geq 1$ , $λ (n)$ is the least positive integer $m$ such that

a^{m} \equiv 1 (mod n) for every a with g cd (a, n) = 1.

Equivalently, $λ (n)$ is the exponent of the group $(Z / n Z)^{\times}$ : the least common multiple of the orders of its elements.

The two descriptions agree because $a^{m} \equiv 1$ for all units is exactly the statement that $m$ is a common multiple of all element orders, and the least such is the lcm.

Theorem 4.80 (Carmichael's formula). $λ (1) = λ (2) = 1$ , $λ (4) = 2$ , and

λ (2^{a}) = 2^{a - 2} (a \geq 3), λ (p^{a}) = φ (p^{a}) = p^{a - 1} (p - 1) (p odd),

while for $n = 2^{a_{0}} p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ ,

λ (n) = lcm (λ (2^{a_{0}}), λ (p_{1}^{a_{1}}), \dots, λ (p_{r}^{a_{r}})) .

Proof. The last formula first. By the Chinese remainder theorem, as in the proof of $φ$ is multiplicative, $(Z / n Z)^{\times} ≅ \prod_{i} (Z / p_{i}^{a_{i}} Z)^{\times}$ . An element of a direct product has order the lcm of the coordinate orders, so the exponent of a product of groups is the lcm of their exponents, which is the displayed formula.

For odd $p$ , the group $(Z / p^{a} Z)^{\times}$ is cyclic of order $φ (p^{a})$ — the existence of a primitive root modulo an odd prime power — and a cyclic group of order $m$ has exponent $m$ , since a generator has order $m$ . Hence $λ (p^{a}) = φ (p^{a})$ .

For $p = 2$ the group is cyclic only for $a \leq 2$ : $(Z /2 Z)^{\times}$ is trivial and $(Z /4 Z)^{\times} = {\pm 1}$ has exponent $2$ . For $a \geq 3$ one has $(Z / 2^{a} Z)^{\times} ≅ {\pm 1} \times ⟨ 5 ⟩$ with $5$ of order $2^{a - 2}$ , so the exponent is $lcm (2, 2^{a - 2}) = 2^{a - 2}$ because $a - 2 \geq 1$ . That $5$ has order $2^{a - 2}$ follows by induction from $5^{2^{k}} = 1 + 2^{k + 2} t$ with $t$ odd, which squares to $1 + 2^{k + 3} t^{'}$ with $t^{'}$ odd.∎

Example 4.81 (Computing $λ$ ). Compute $λ (n)$ for $n = 8, 15, 16, 65, 561$ .

Solution.

$λ (8) = 2^{3 - 2} = 2$ : every odd square is $1$ mod $8$ .
$λ (15) = lcm (λ (3), λ (5)) = lcm (2, 4) = 4$ , while $φ (15) = 8$ .
$λ (16) = 2^{4 - 2} = 4$ , while $φ (16) = 8$ .
$λ (65) = lcm (4, 12) = 12$ , while $φ (65) = 48$ .
$561 = 3 \cdot 11 \cdot 17$ , so $λ (561) = lcm (2, 10, 16) = 80$ , while $φ (561) = 2 \cdot 10 \cdot 16 = 320$ .

□

Exercises for §4.18 →

4.19 $λ$ against $φ$

Theorem 4.82 ( $λ$ divides $φ$ ). For every $n \geq 1$ , $λ (n) ∣ φ (n)$ , and $λ (n) \leq φ (n)$ . Equality holds if and only if $(Z / n Z)^{\times}$ is cyclic, that is if and only if $n \in {1, 2, 4, p^{a}, 2 p^{a}}$ for an odd prime $p$ .

Proof. The exponent of a finite group divides its order: if $m$ is the exponent and $g$ any element, the order of $g$ divides $m$ , and by Lagrange every element order divides $∣ G ∣$ , so $m = lcm$ of element orders divides $∣ G ∣$ as well — each element order divides $∣ G ∣$ , hence so does their lcm. With $∣ G ∣ = φ (n)$ by $φ$ counts units and $m = λ (n)$ by definition, $λ (n) ∣ φ (n)$ .

Equality $λ (n) = φ (n)$ means some element has order $∣ G ∣$ , that is $G$ is cyclic; this is the classification of the $n$ possessing a primitive root, namely $n = 1, 2, 4, p^{a}, 2 p^{a}$ . For any other $n$ the Chinese remainder decomposition has at least two factors of even order, or the factor $(Z / 2^{a} Z)^{\times}$ with $a \geq 3$ , and in both cases the lcm is a proper divisor of the product.∎

Corollary 4.83 (A sharper Euler theorem). If $g cd (a, n) = 1$ then $a^{λ (n)} \equiv 1 (mod n)$ , and this recovers Euler's theorem since $λ (n) ∣ φ (n)$ .

Proof. The first statement is the definition of $λ$ . For the second, write $φ (n) = λ (n) k$ ; then $a^{φ (n)} = (a^{λ (n)})^{k} \equiv 1^{k} = 1$ .∎

Example 4.84 (Where $λ$ beats $φ$ ). Compute the order of $3$ modulo $16$ and compare with $λ (16)$ and $φ (16)$ .

Solution.

$3^{2} = 9$ , $3^{4} = 81 = 5 \cdot 16 + 1 \equiv 1 (mod 16)$ .
So $3$ has order $4 = λ (16)$ , and no unit modulo $16$ has order $8 = φ (16)$ .
Euler's exponent $φ (16) = 8$ is therefore twice as large as it needs to be; in a modular exponentiation this is a factor-of-two waste, which is why $λ$ rather than $φ$ is the exponent used in RSA key generation.

□

Remark. The gap can be enormous. For $n = 2 \cdot 3 \cdot 5 \dots p_{r}$ a primorial, $φ (n) = \prod (p_{i} - 1)$ while $λ (n) = lcm (p_{i} - 1)$ , and the lcm discards all the shared factors of $2$ : for $n = 510510$ one has $φ (n) = 92160$ but $λ (n) = 144$ .

Exercises for §4.19 →

4.20Carmichael numbers and Korselt's criterion

Fermat's little theorem gives a primality test: if $a^{n - 1} \neq \equiv 1 (mod n)$ for some $a$ coprime to $n$ , then $n$ is composite. The test has false positives, and the numbers that fool it for every base are the subject here.

Definition 4.85 (Carmichael number). A composite $n$ is a Carmichael number if

a^{n - 1} \equiv 1 (mod n) for every a with g cd (a, n) = 1.

Equivalently, $a^{n} \equiv a (mod n)$ for every integer $a$ .

Theorem 4.86 (Korselt's criterion). A composite $n$ is a Carmichael number if and only if $n$ is squarefree and

p - 1 n - 1 for every prime p ∣ n .

Proof. ( $\Leftarrow$ ) Suppose $n = p_{1} \dots p_{k}$ is squarefree with each $p_{i} - 1 ∣ n - 1$ , and let $g cd (a, n) = 1$ . Then $p_{i} ∤ a$ , so Fermat's little theorem gives $a^{p_{i} - 1} \equiv 1 (mod p_{i})$ , and since $p_{i} - 1$ divides $n - 1$ we may raise to the appropriate power: $a^{n - 1} \equiv 1 (mod p_{i})$ for each $i$ . The $p_{i}$ are distinct primes, so by the Chinese remainder theorem $a^{n - 1} \equiv 1 (mod n)$ .

( $\Rightarrow$ ) Suppose $n$ is composite and $a^{n - 1} \equiv 1$ for every $a$ coprime to $n$ . By the definition of the Carmichael function as the least such exponent, $λ (n) ∣ n - 1$ . Since $g cd (n, n - 1) = 1$ , it follows that $g cd (λ (n), n) = 1$ .

Squarefree. Suppose $p^{2} ∣ n$ for some prime $p$ . If $p$ is odd, Carmichael's formula gives $λ (p^{a}) = p^{a - 1} (p - 1)$ with $a \geq 2$ , so $p ∣ λ (p^{a}) ∣ λ (n)$ , contradicting $g cd (λ (n), n) = 1$ . If $p = 2$ , then $4 ∣ n$ , so $n$ is even, $n - 1$ is odd, yet $λ (4) = 2$ divides $λ (n) ∣ n - 1$ — again a contradiction. Hence $n$ is squarefree.

The divisibility. Now $n = p_{1} \dots p_{k}$ with distinct primes. If some $p_{i}$ is odd, then $p_{i} - 1$ is even, so $2 ∣ λ (n) ∣ n - 1$ , forcing $n$ odd; and if all $p_{i} = 2$ then $n = 2$ is not composite. So $n$ is odd and every $p_{i}$ is odd. By Carmichael's formula, $λ (n) = lcm_{i} (p_{i} - 1)$ , and each $p_{i} - 1$ divides that lcm, which divides $n - 1$ . Hence $p_{i} - 1 ∣ n - 1$ for every $i$ .∎

Corollary 4.87 (A Carmichael number has at least three prime factors). Every Carmichael number is odd and is a product of at least three distinct primes.

Proof. Oddness was established inside the proof of Korselt's criterion. Suppose $n = pq$ with $p < q$ distinct odd primes. Korselt requires $q - 1 ∣ n - 1 = pq - 1$ . But $pq - 1 = p (q - 1) + (p - 1)$ , so $q - 1 ∣ p - 1$ , which is impossible since $0 < p - 1 < q - 1$ . Hence $k \neq = 2$ , and $k = 1$ would make $n$ prime, so $k \geq 3$ .∎

Example 4.88 (Verifying $561$ ). Show that $561$ is a Carmichael number and that $1105$ is as well.

Solution.

$561 = 3 \cdot 11 \cdot 17$ , squarefree, and $n - 1 = 560$ .
$3 - 1 = 2 ∣ 560$ ; $11 - 1 = 10 ∣ 560$ since $560 = 10 \cdot 56$ ; $17 - 1 = 16 ∣ 560$ since $560 = 16 \cdot 35$ .
All three conditions hold and $561$ is composite, so Korselt's criterion certifies it. It is the smallest Carmichael number.
$1105 = 5 \cdot 13 \cdot 17$ with $n - 1 = 1104$ : $4 ∣ 1104$ ( $= 4 \cdot 276$ ), $12 ∣ 1104$ ( $= 12 \cdot 92$ ), $16 ∣ 1104$ ( $= 16 \cdot 69$ ). So $1105$ is Carmichael too.

□

Example 4.89 (A number Korselt rejects). Is $1729 = 7 \cdot 13 \cdot 19$ a Carmichael number? Is $15 = 3 \cdot 5$ ?

Solution.

For $1729$ : $n - 1 = 1728$ . Check $6 ∣ 1728$ ( $= 6 \cdot 288$ ), $12 ∣ 1728$ ( $= 12 \cdot 144$ ), $18 ∣ 1728$ ( $= 18 \cdot 96$ ). All hold, so $1729$ is Carmichael.
For $15$ : it has only two prime factors, so A Carmichael number has at least three prime factors rules it out at once. Concretely $5 - 1 = 4$ does not divide $14$ .
Indeed $2^{14} = 16384 = 15 \cdot 1092 + 4 \equiv 4 (mod 15)$ , so base $2$ detects that $15$ is composite.

□

Remark. Carmichael numbers are rare but infinite in number: Alford, Granville and Pomerance proved in 1994 that there are at least $x^{2/7}$ of them below $x$ . Their existence is why the Fermat test is replaced in practice by the Miller–Rabin test, which has no analogue of a Carmichael number — no composite is a strong pseudoprime to more than a quarter of the bases.

Exercises for §4.20 →

4.21Dirichlet convolution

The operation has been used throughout; here it is defined properly and its elementary properties are established.

Definition 4.90 (Dirichlet convolution). For arithmetic functions $f, g$ , their Dirichlet convolution is the arithmetic function

(f * g) (n) = d ∣ n \sum f (d) g (\frac{n}{d}) = ab = n a, b \geq 1 \sum f (a) g (b) .

The second form is the one to use in proofs: it is manifestly symmetric in $f$ and $g$ , and it generalises immediately to three or more factors.

Proposition 4.91 (Commutativity). $f * g = g * f$ for all arithmetic functions $f, g$ .

Proof. In the symmetric form, $(f * g) (n) = \sum_{ab = n} f (a) g (b)$ . Swapping the names of the summation variables turns this into $\sum_{ba = n} f (b) g (a) = \sum_{ab = n} g (a) f (b) = (g * f) (n)$ , since the condition $ab = n$ is symmetric and multiplication in $C$ is commutative.∎

Proposition 4.92 (The delta function is an identity). $f * ε = ε * f = f$ for every $f$ .

Proof. $(f * ε) (n) = \sum_{d ∣ n} f (d) ε (n / d)$ , and $ε (n / d) = 0$ unless $n / d = 1$ , that is unless $d = n$ . The single surviving term is $f (n) ε (1) = f (n)$ . Commutativity gives the other order.∎

Example 4.93 (Convolution by hand). Compute $(μ * σ) (12)$ and $(φ * φ) (12)$ .

Solution.

Divisors of $12$ : $1, 2, 3, 4, 6, 12$ with $μ$ -values $1, - 1, - 1, 0, 1, 0$ and $σ$ -values $1, 3, 4, 7, 12, 28$ .
$(μ * σ) (12) = μ (1) σ (12) + μ (2) σ (6) + μ (3) σ (4) + μ (4) σ (3) + μ (6) σ (2) + μ (12) σ (1) = 28 - 12 - 7 + 0 + 3 + 0 = 12$ .
That is no accident: $σ = id * u$ , so $μ * σ = μ * u * id = ε * id = id$ , giving $12$ .
$(φ * φ) (12) = φ (1) φ (12) + φ (2) φ (6) + φ (3) φ (4) + φ (4) φ (3) + φ (6) φ (2) + φ (12) φ (1) = 4 + 2 + 4 + 4 + 2 + 4 = 20$ .

□

Figure 4.94. The divisor lattice of

30

. An edge joins

d

d p

for a prime

p

; a Dirichlet convolution at

n = 30

sums over all eight vertices, pairing each

d

with the vertex diagonally opposite it,

30/ d

Exercises for §4.21 →

4.22The ring of arithmetic functions

Theorem 4.95 (Associativity of convolution). For all arithmetic functions $f, g, h$ ,

(f * g) * h = f * (g * h), with common value n \mapsto ab c = n \sum f (a) g (b) h (c),

the sum over ordered triples of positive integers with product $n$ .

Proof. Expand the left-hand side using the symmetric form of the definition twice:

((f * g) * h) (n) = d e = n \sum (f * g) (d) h (e) = d e = n \sum ab = d \sum f (a) g (b) h (e) .

A pair $(d, e)$ with $d e = n$ together with a pair $(a, b)$ with $ab = d$ is the same data as a triple $(a, b, e)$ with $ab e = n$ : given the triple, $d = ab$ is determined, and given the pairs, the triple is read off. So the double sum is exactly $\sum_{ab c = n} f (a) g (b) h (c)$ .

The same expansion on the right gives

(f * (g * h)) (n) = a d^{'} = n \sum f (a) (g * h) (d^{'}) = a d^{'} = n \sum b c = d^{'} \sum f (a) g (b) h (c),

and pairs $(a, d^{'})$ with $a d^{'} = n$ together with $(b, c)$ with $b c = d^{'}$ are again the same data as triples $(a, b, c)$ with $ab c = n$ . Both sides equal the symmetric triple sum, so they are equal.∎

Theorem 4.96 (Convolution makes a commutative ring). The set $A$ of arithmetic functions, with pointwise addition and Dirichlet convolution, is a commutative ring with identity $ε$ . It is moreover an integral domain.

Proof. Addition makes $A$ an abelian group, as it is pointwise addition of complex-valued functions. Convolution is commutative by Commutativity, associative by Associativity of convolution, and has identity $ε$ by The delta function is an identity. Distributivity is immediate from the definition, since

(f * (g + h)) (n) = ab = n \sum f (a) (g (b) + h (b)) = (f * g) (n) + (f * h) (n) .

For the domain property, let $f, g$ be nonzero and let $m$ , $m^{'}$ be the least integers with $f (m) \neq = 0$ , $g (m^{'}) \neq = 0$ . Consider $(f * g) (m m^{'}) = \sum_{ab = m m^{'}} f (a) g (b)$ . A term is nonzero only if $a \geq m$ and $b \geq m^{'}$ ; combined with $ab = m m^{'}$ this forces $a = m$ , $b = m^{'}$ . So $(f * g) (m m^{'}) = f (m) g (m^{'}) \neq = 0$ and $f * g \neq = 0$ .∎

Theorem 4.97 (Units of the Dirichlet ring). An arithmetic function $f$ has a convolution inverse if and only if $f (1) \neq = 0$ . The inverse $f^{- 1}$ is then unique and determined recursively by

f^{- 1} (1) = \frac{1}{f ( 1 )}, f^{- 1} (n) = - \frac{1}{f ( 1 )} d ∣ n d < n \sum f (\frac{n}{d}) f^{- 1} (d) (n > 1) .

Proof. If $f * g = ε$ then evaluating at $n = 1$ gives $f (1) g (1) = 1$ , so $f (1) \neq = 0$ .

Conversely suppose $f (1) \neq = 0$ . We construct $g$ with $f * g = ε$ by strong induction on $n$ . At $n = 1$ , $(f * g) (1) = f (1) g (1)$ must equal $1$ , which forces and permits $g (1) = 1/ f (1)$ . For $n > 1$ the requirement is

0 = ε (n) = (f * g) (n) = d ∣ n \sum f (n / d) g (d) = f (1) g (n) + d ∣ n d < n \sum f (n / d) g (d),

which determines $g (n)$ uniquely as the displayed expression, every $g (d)$ occurring in it having $d < n$ and so being already defined. The resulting $g$ satisfies $f * g = ε$ at every $n$ by construction, and uniqueness at each step gives uniqueness of $g$ .∎

Example 4.98 (Inverting $u$ from the recursion). Use the recursion of Units of the Dirichlet ring to compute $u^{- 1} (n)$ for $n \leq 6$ .

Solution.

$u^{- 1} (1) = 1$ .
$u^{- 1} (2) = - (u (2) u^{- 1} (1)) = - 1$ ; likewise $u^{- 1} (3) = u^{- 1} (5) = - 1$ .
$u^{- 1} (4) = - (u^{- 1} (1) + u^{- 1} (2)) = - (1 - 1) = 0$ .
$u^{- 1} (6) = - (u^{- 1} (1) + u^{- 1} (2) + u^{- 1} (3)) = - (1 - 1 - 1) = 1$ .
The values $1, - 1, - 1, 0, - 1, 1$ are exactly $μ (1), \dots, μ (6)$ , as The Möbius sum identity predicts: $u^{- 1} = μ$ .

□

Corollary 4.99 (Möbius inversion restated). $u$ and $μ$ are mutually inverse units of $A$ , and Möbius inversion is precisely the statement that convolution by a unit is a bijection of $A$ with inverse convolution by the inverse unit.

Proof. $μ * u = ε$ by The Möbius sum identity, so each is the inverse of the other by uniqueness in Units of the Dirichlet ring. In any ring, multiplication by a unit $v$ is a bijection with inverse multiplication by $v^{- 1}$ ; applied to $v = u$ this reads $g = f * u ⟺ f = g * μ$ , which is the inversion formula.∎

Remark. The ring $A$ is in fact a local ring: its non-units are exactly the $f$ with $f (1) = 0$ , and those form an ideal, since a sum of two such has $f (1) + g (1) = 0$ and a product has $(f * g) (1) = f (1) g (1) = 0$ . It is also isomorphic to a ring of formal power series in countably many variables, one per prime — a fact that makes the Euler product look like a change of coordinates.

Exercises for §4.22 →

4.23The group of multiplicative functions

Inside the ring $A$ , the multiplicative functions form a group. This is the cleanest statement of the chapter's organising principle, and everything else has been proved already.

Theorem 4.100 (Multiplicative functions form a group). The set $M$ of multiplicative functions is an abelian group under Dirichlet convolution, with identity $ε$ . In particular the convolution inverse of a multiplicative function is multiplicative.

Proof. Closure is Convolution preserves multiplicativity; associativity and commutativity are inherited from $A$ ; and $ε$ is multiplicative and is the identity by The delta function is an identity. Every $f \in M$ has $f (1) = 1 \neq = 0$ , so by Units of the Dirichlet ring it has a unique inverse $g$ in $A$ ; it remains to see $g$ is multiplicative.

Let $h$ be the multiplicative function defined on prime powers by $h (p^{a}) = g (p^{a})$ — this exists by the converse half of A multiplicative function is determined by its prime powers. Then $f * h$ is multiplicative, and at a prime power

(f * h) (p^{a}) = j = 0 \sum a f (p^{a - j}) h (p^{j}) = j = 0 \sum a f (p^{a - j}) g (p^{j}) = (f * g) (p^{a}) = ε (p^{a}) .

Two multiplicative functions agreeing on all prime powers are equal, so $f * h = ε$ . By uniqueness of inverses, $h = g$ , and $g$ is multiplicative.∎

Corollary 4.101 (The completely multiplicative inverse). If $f$ is completely multiplicative then $f^{- 1} = μ f$ , the pointwise product. In particular $u^{- 1} = μ$ and $id^{- 1} = μ id$ .

Proof. Both $μ f$ and $f$ are multiplicative — the first by Products and quotients — so $(μ f) * f$ is multiplicative and may be checked at prime powers. There,

((μ f) * f) (p^{a}) = j = 0 \sum a μ (p^{j}) f (p^{j}) f (p^{a - j}) = f (p^{a}) - f (p) f (p^{a - 1}),

since $μ (p^{j}) = 0$ for $j \geq 2$ and $f (p^{j}) f (p^{a - j}) = f (p^{a})$ by complete multiplicativity. For $a \geq 1$ the two terms are both $f (p^{a})$ and cancel, and for $a = 0$ the value is $1$ . That is $ε$ .∎

Example 4.102 (Convolution identities as algebra). Derive $φ = μ * id$ and $\sum_{d ∣ n} μ (d) d (n / d) = 1$ purely by algebra in $M$ .

Solution.

Gauss's identity is $φ * u = id$ . Convolving both sides with $u^{- 1} = μ$ gives $φ = μ * id$ .
$d = u * u$ , so $μ * d = μ * u * u = ε * u = u$ .
Evaluating the second at any $n$ gives $\sum_{d ∣ n} μ (d) d (n / d) = u (n) = 1$ .
Similarly $μ * σ = μ * u * id = id$ , so $\sum_{d ∣ n} μ (d) σ (n / d) = n$ .

□

Example 4.103 (An inverse computed at prime powers). Find the convolution inverse of $d$ .

Solution.

$d = u * u$ , so $d^{- 1} = μ * μ$ by uniqueness of inverses in a commutative ring.
At a prime power, $(μ * μ) (p^{a}) = \sum_{j} μ (p^{j}) μ (p^{a - j})$ , which is $1$ for $a = 0$ , $- 2$ for $a = 1$ , $1$ for $a = 2$ , and $0$ for $a \geq 3$ .
So $d^{- 1}$ is the multiplicative function with $d^{- 1} (p) = - 2$ , $d^{- 1} (p^{2}) = 1$ , and $d^{- 1} (p^{a}) = 0$ for $a \geq 3$ ; for instance $d^{- 1} (12) = d^{- 1} (4) d^{- 1} (3) = 1 \cdot (- 2) = - 2$ .

□

Pitfall. The group $M$ is closed under convolution but not under addition: $ε + ε$ is not multiplicative, as noted in Products and quotients. $M$ is a subgroup of the unit group of $A$ , never a subring.

Exercises for §4.23 →

4.24Mertens' three theorems

The chapter closes with the average behaviour of the primes. The three statements below were proved by Mertens in 1874, two decades before the prime number theorem, and two of the three are genuinely elementary: they need only Chebyshev-type bounds and careful summation. They are the quantitative form of "the primes thin out like $1/ ln x$ ".

Theorem 4.104 (Mertens' first theorem). For $x \geq 2$ ,

p \leq x \sum \frac{ln p}{p} = ln x + O (1),

the sum over primes $p \leq x$ , with the implied constant absolute.

Theorem 4.105 (Mertens' second theorem). There is a constant $M \approx 0.2614972$ , the Meissel–Mertens constant, with

p \leq x \sum \frac{1}{p} = ln ln x + M + O (\frac{1}{ln x}) .

Theorem 4.106 (Mertens' third theorem). With $γ$ the Euler–Mascheroni constant,

p \leq x \prod (1 - \frac{1}{p}) = \frac{e ^{- γ}}{ln x} (1 + O (\frac{1}{ln x})) .

The three are a chain: the first is the raw input, the second follows from it by partial summation, and the third follows from the second by taking logarithms — except for the value of the constant, which is the one genuinely hard point and the only place where analytic machinery is unavoidable.

Remark. The second theorem says the sum of reciprocals of primes diverges, and tells us how: like $ln ln x$ , which is the slowest divergence one is likely to meet. To make $\sum_{p \leq x} 1/ p$ exceed $4$ one needs $x$ beyond $1 0^{18}$ . Compare $\sum_{n \leq x} 1/ n = ln x + γ + O (1/ x)$ : the primes are sparse enough to cost an entire logarithm.

Intuition. If "the probability that $n$ is prime" is $1/ ln n$ , then $\sum_{p \leq x} 1/ p$ should behave like $\int_{2}^{x} \frac{d t}{t l n t} = ln ln x + C$ , which is exactly Mertens' second theorem. The heuristic gets the shape right and says nothing about the constant $M$ — which is the honest summary of the situation.

Exercises for §4.24 →

4.25Proving the three theorems

Lemma 4.107 (Legendre's factorial formula). For $n \geq 1$ ,

ln (n!) = p \leq n \sum k \geq 1 \sum ⌊ \frac{n}{p ^{k}} ⌋ ln p .

Proof. By unique factorisation, $n! = \prod_{p \leq n} p^{v_{p}}$ where $v_{p}$ is the exponent of $p$ in $n!$ . Counting the multiples of $p$ , then of $p^{2}$ , and so on among $1, \dots, n$ , each multiple of $p^{k}$ contributing one to the count for every $j \leq k$ , gives $v_{p} = \sum_{k \geq 1} ⌊ n / p^{k} ⌋$ , a finite sum. Taking logarithms gives the formula.∎

Proof (Proof of Mertens' first theorem). Apply Legendre's factorial formula and split off $k = 1$ :

ln (n!) = p \leq n \sum ⌊ \frac{n}{p} ⌋ ln p + p \leq n \sum k \geq 2 \sum ⌊ \frac{n}{p ^{k}} ⌋ ln p .

The second sum is $O (n)$ : bounding each floor by $n / p^{k}$ and summing the geometric series gives at most $n \sum_{p} \frac{l n p}{p ( p - 1 )}$ , and that series converges, being dominated by $\sum_{m} \frac{l n m}{m ( m - 1 )}$ .

In the first sum write $⌊ n / p ⌋ = n / p + O (1)$ . The error contributes $O (\sum_{p \leq n} ln p) = O (n)$ , using Chebyshev's estimate $\sum_{p \leq n} ln p = O (n)$ — itself elementary, from the fact that the binomial coefficient $(m 2 m)$ is divisible by every prime in $(m, 2 m]$ and is at most $4^{m}$ . Hence

ln (n!) = n p \leq n \sum \frac{ln p}{p} + O (n) .

Stirling's formula in its crude form gives $ln (n!) = n ln n + O (n)$ . Equating and dividing by $n$ ,

p \leq n \sum \frac{ln p}{p} = ln n + O (1) .

Finally, for real $x$ the sum over $p \leq x$ equals the sum over $p \leq ⌊ x ⌋$ and $ln ⌊ x ⌋ = ln x + O (1)$ , giving the statement for all $x \geq 2$ .∎

Proof (Proof of Mertens' second theorem). Let $A (t) = \sum_{p \leq t} \frac{l n p}{p}$ , so that $A (t) = ln t + R (t)$ with $R$ bounded, by Mertens' first theorem. Write $\frac{1}{p} = \frac{l n p}{p} \cdot \frac{1}{l n p}$ and apply partial summation with the weight $1/ ln t$ :

p \leq x \sum \frac{1}{p} = \frac{A ( x )}{ln x} + \int_{2}^{x} \frac{A ( t )}{t ln ^{2} t} d t .

Substituting $A (t) = ln t + R (t)$ , the first term is $1 + O (1/ ln x)$ and the integral splits as

\int_{2}^{x} \frac{d t}{t ln t} + \int_{2}^{x} \frac{R ( t )}{t ln ^{2} t} d t = ln ln x - ln ln 2 + \int_{2}^{\infty} \frac{R ( t ) d t}{t ln ^{2} t} - \int_{x}^{\infty} \frac{R ( t ) d t}{t ln ^{2} t} .

The infinite integral converges absolutely because $R$ is bounded and $\int_{2}^{\infty} \frac{d t}{t l n ^{2} t}$ is finite, and the same bound makes the tail $O (1/ ln x)$ . Collecting the constants into a single $M$ gives the theorem. The numerical value $M = γ + \sum_{p} (ln (1 - 1/ p) + 1/ p)$ follows by comparing with the third theorem.∎

Proof (Sketch of Mertens' third theorem). Take logarithms of the product and expand:

ln p \leq x \prod (1 - \frac{1}{p}) = p \leq x \sum ln (1 - \frac{1}{p}) = - p \leq x \sum \frac{1}{p} - p \leq x \sum k \geq 2 \sum \frac{1}{k p ^{k}} .

The double sum converges absolutely as $x \to \infty$ , to a constant $- C$ say, with tail $O (1/ x)$ . By Mertens' second theorem the whole expression is $- ln ln x - M + C + O (1/ ln x)$ , so

p \leq x \prod (1 - \frac{1}{p}) = \frac{e ^{C - M}}{ln x} (1 + O (\frac{1}{ln x})) .

Everything to this point is elementary. What is not elementary is the evaluation $C - M = - γ$ . This is where the sketch stops being a proof: identifying the constant requires comparing the Euler product of $ζ$ near $s = 1$ with the pole $ζ (s) \sim 1/ (s - 1)$ and using $Γ$ -function asymptotics, or equivalently invoking the prime number theorem in the form $\sum_{p \leq x} ln p = x + o (x / ln x)$ . Assuming that input, the constant comes out as $e^{- γ}$ and the theorem follows.∎

Remark. It is worth being precise about what is assumed where. Mertens' first and second theorems are proved above from Stirling's formula and Chebyshev's bound, both elementary; no zero-free region and no prime number theorem is used, and indeed Mertens proved them before the PNT existed. Only the constant in the third theorem needs more, and the shape $c / ln x$ of the third theorem does not.

Exercises for §4.25 →

4.26What the theorems are used for

Proposition 4.108 (The density of coprime pairs to a primorial). Let $P_{r} = p_{1} p_{2} \dots p_{r}$ be the product of the first $r$ primes. Then

\frac{φ ( P _{r} )}{P _{r}} = i \leq r \prod (1 - \frac{1}{p _{i}}) \sim \frac{e ^{- γ}}{ln p _{r}} ⟶ 0.

Hence $lim inf_{n} φ (n) / n = 0$ .

Proof. The product formula is Euler's product formula applied to the squarefree $P_{r}$ . The asymptotic is Mertens' third theorem with $x = p_{r}$ , since the primes $\leq p_{r}$ are exactly $p_{1}, \dots, p_{r}$ . The right-hand side tends to $0$ because there are infinitely many primes, so $p_{r} \to \infty$ , and exhibiting a sequence along which $φ (n) / n \to 0$ establishes the liminf.∎

Example 4.109 (How small can $φ (n) / n$ get?). Estimate $φ (n) / n$ for $n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$ and compare with Mertens' prediction.

Solution.

Exactly: $φ (30030) = 1 \cdot 2 \cdot 4 \cdot 6 \cdot 10 \cdot 12 = 5760$ , so $φ (30030) /30030 = 5760/30030 = 0.19181 \dots$
Mertens predicts $e^{- γ} / ln 13 = 0.5615/2.5649 = 0.2189$ .
The agreement is about $14%$ — unimpressive, and exactly what one expects from an asymptotic with a relative error of order $1/ ln x = 0.39$ at this size. The approximation is a statement about $p_{r} \to \infty$ , not about $p_{r} = 13$ .

□

Proposition 4.110 (Sieve heuristic bound). The number of integers in $[1, x]$ with no prime factor below $z$ is at most $C x \prod_{p < z} (1 - 1/ p) + O (2^{π (z)})$ for an absolute constant $C$ , which by Mertens' third theorem is $O (x / ln z)$ .

Proof. By inclusion–exclusion over the squarefree $d$ built from primes below $z$ , the count is $\sum_{d} μ (d) ⌊ x / d ⌋$ , which equals $x \prod_{p < z} (1 - 1/ p)$ plus an error of at most one per term, and there are $2^{π (z)}$ terms. Applying Mertens' third theorem to the product gives the stated order $x e^{- γ} / ln z$ .∎

Remark. Taking $z = x$ in the last proposition would count the primes up to $x$ and give $π (x) = O (x / ln x)$ — except that the error term $2^{π (x)}$ swamps the main term long before that. Controlling that error is the entire subject of sieve theory, and the Legendre sieve above is its crudest form.

Exercises for §4.26 →

4.27Mertens, the zeta function and the Euler product

The third theorem has a clean interpretation in terms of $ζ$ , which also explains where $e^{- γ}$ comes from.

Proposition 4.111 (The product and the pole). For $s > 1$ real,

p \prod (1 - \frac{1}{p ^{s}})^{- 1} = ζ (s) = \frac{1}{s - 1} + γ + O (s - 1) as s \to 1^{+} .

Thus the Euler product diverges as $s \to 1^{+}$ at exactly the rate $1/ (s - 1)$ , and the constant term of the Laurent expansion is $γ$ .

Proof. The product formula is Euler's product for zeta. For the expansion, compare with the integral:

ζ (s) - \frac{1}{s - 1} = n \geq 1 \sum \frac{1}{n ^{s}} - \int_{1}^{\infty} \frac{d t}{t ^{s}} = n \geq 1 \sum \int_{n}^{n + 1} (\frac{1}{n ^{s}} - \frac{1}{t ^{s}}) d t .

Each integrand is bounded by $s / n^{s + 1}$ in absolute value, so the series converges uniformly for $s$ in a neighbourhood of $1$ and defines a continuous function there. Its value at $s = 1$ is $\sum_{n} \int_{n}^{n + 1} (1/ n - 1/ t) d t = lim_{N} (\sum_{n \leq N} 1/ n - ln N) = γ$ , which is the definition of the Euler–Mascheroni constant.∎

Remark. Compare the two appearances of $γ$ . In The product and the pole it arises from the difference between a harmonic sum and a logarithm; in Mertens' third theorem it appears in the exponent, $e^{- γ}$ . They are the same constant for the same reason: the finite Euler product $\prod_{p \leq x} (1 - 1/ p)^{- 1}$ must approximate $ζ (s)$ with $s - 1 \approx 1/ ln x$ , and matching $ζ (s) \approx 1/ (s - 1) + γ$ against $ln x$ produces exactly the factor $e^{γ}$ . Making that matching rigorous is the analytic step the sketch above declined to take.

Proposition 4.112 (Möbius and the reciprocal of zeta). For $Re (s) > 1$ , $\sum_{n \geq 1} μ (n) n^{- s} = 1/ ζ (s)$ , and the statement $M (x) = o (x)$ is equivalent to $ζ (1 + i t) \neq = 0$ for all real $t$ , hence to the prime number theorem.

Proof. The series identity is The series of $μ$ , $d$ and $σ_{k}$ . For the equivalence we only prove the easy direction: if $M (x) = o (x)$ then partial summation shows $\sum μ (n) n^{- s}$ converges for $Re (s) \geq 1$ , so $1/ ζ (s)$ extends continuously to the line $Re (s) = 1$ , forcing $ζ (1 + i t) \neq = 0$ . The converse, that non-vanishing on the line implies $M (x) = o (x)$ , is a Tauberian theorem and is not proved here.∎

Example 4.113 (Reading off a density from a zeta quotient). The Dirichlet series of $μ^{2}$ is $ζ (s) / ζ (2 s)$ . What density does that predict, and why?

Solution.

As $s \to 1^{+}$ , $ζ (s)$ has a simple pole with residue $1$ while $ζ (2 s) \to ζ (2) = π^{2} /6$ .
So $ζ (s) / ζ (2 s) \sim \frac{6/ π ^{2}}{s - 1}$ : a simple pole of residue $6/ π^{2}$ .
A residue $c$ at $s = 1$ corresponds to a summatory function $\sim c x$ , so the squarefree integers have density $6/ π^{2} \approx 0.6079$ — matching the direct count in Counting squarefree integers up to $x$ .

□

Exercises for §4.27 →

Common Mistakes

Reading "multiplicative" as linear. $f (m + n)$ has nothing to do with $f (m)$ and $f (n)$ ; and $f (mn) = f (m) f (n)$ needs $g cd (m, n) = 1$ unless $f$ is completely multiplicative. $φ (4) = 2$ , not $φ (2)^{2} = 1$ .
Forgetting the exponent in $φ (p^{a})$ . The value is $p^{a} - p^{a - 1}$ , not $p - 1$ . The bracket form $n \prod_{p ∣ n} (1 - 1/ p)$ sees only the distinct primes because the exponents are already inside the leading $n$ .
Checking an identity at primes only. Two multiplicative functions can agree at every prime and differ everywhere else; the correct check is at every prime power. This is what separates $d$ from $2^{ω}$ , which agree at all primes.
Writing $\sum_{d ∣ n} μ (d) g (d)$ in the inversion formula. The pairing is $μ (d) g (n / d)$ ; the arguments must multiply to $n$ .
Applying Möbius inversion to one value of $n$ . The hypothesis $g = f * u$ must hold at every positive integer; knowing it at a single $n$ says nothing.
Assuming $λ (n) = φ (n)$ . Equality holds only when a primitive root exists, that is for $n = 1, 2, 4, p^{a}, 2 p^{a}$ . For $n = 15$ the correct exponent is $4$ , not $8$ .
Treating $ε$ and $u$ as the same thing. $ε$ is the convolution identity and is supported at $n = 1$ ; $u$ is constantly $1$ and is the summing operator. Convolving with $u$ takes divisor sums; convolving with $ε$ does nothing.
Calling every Fermat pseudoprime a Carmichael number. A Carmichael number must fool the test for every coprime base, which by Korselt's criterion forces squarefreeness and at least three prime factors. $341 = 11 \cdot 31$ is a pseudoprime to base $2$ only.
Expecting $σ (n) / n$ or $φ (n) / n$ to converge. Neither has a limit; both have a whole interval of limit points. Only averages and the extreme behaviour described by Mertens' theorems are stable.
Adding multiplicative functions. A sum of two multiplicative functions has value $2$ at $n = 1$ and so is never multiplicative. The closure properties are pointwise product, quotient by a nowhere-zero function, and Dirichlet convolution.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter

Introduction

4.1Definitions and basic classes

4.2Values, order of magnitude, and the ring structure

4.3Generating functions and Dirichlet series

4.4Multiplicative functions in practice

4.5Convolution preserves multiplicativity

4.6Euler products for multiplicative functions

4.7Euler's totient: definition and first values

4.8The product formula, via inclusion–exclusion

4.9Multiplicativity, Euler's theorem, and the second proof

4.10Divisor sums of the totient

4.11The Möbius function

4.12Möbius inversion

4.13The sum identity and what it does

4.14Applications of Möbius inversion

4.15Divisor functions

4.16Formulas and Dirichlet series for σk​

4.17Perfect numbers and the Euclid–Euler theorem

4.18The Carmichael function

4.19λ against φ

4.20Carmichael numbers and Korselt's criterion

4.21Dirichlet convolution

4.22The ring of arithmetic functions

4.23The group of multiplicative functions

4.24Mertens' three theorems

4.25Proving the three theorems

4.26What the theorems are used for

4.27Mertens, the zeta function and the Euler product

4.16Formulas and Dirichlet series for $σ_{k}$

4.19 $λ$ against $φ$