Motivation
A divisor sum mixes information from an integer and all its divisors. For example, counting fractions with denominator dividing gives a total involving for every . Möbius inversion recovers the contribution at the exact integer . Before inverting, we need a way to calculate divisor sums without listing every divisor separately.
Definitions
Definition 4.1.1
(Arithmetic functions and multiplicativity)
An arithmetic function is a function on the positive integers, with complex values here. It is multiplicative if and whenever . It is completely multiplicative if the product identity holds without the coprimality restriction. Define
Set ; set when a prime square divides ; otherwise set when is the product of distinct primes. Extend Euler's function by .
The word multiplicative always retains its coprimality condition unless stated otherwise. A multiplicative function is determined by its values on prime powers, because unique factorization decomposes into pairwise coprime prime-power factors.
Theorem/Proposition
Theorem 4.1.2
(Prime-power products)
For with distinct primes and positive exponents,
All three functions are multiplicative.
Theorem 4.1.3
(Möbius inversion)
For arithmetic functions , the identities for all positive hold if and only if
for all positive . In particular and .
Proof sketch or proof idea
Proof
(Exponent tuples and inclusion–exclusion)
Every divisor of corresponds uniquely to a tuple of exponents . Counting tuples proves the formula for ; summing and distributing proves the formula for . To compute , count among the integers divisible by none of the . Inclusion–exclusion subtracts , adds , and so on. Its expansion is . The disjoint prime supports of coprime inputs prove multiplicativity.
Proof
(Cancellation and a rearranged finite sum)
The key cancellation identity is
Only squarefree divisors contribute. If has distinct prime factors, their contributions sum to . For the only divisor is .
Now substitute the divisor sum for and rearrange finite sums:
Conversely substitute the proposed formula for into and use the same inner cancellation to obtain . No convergence argument is needed: every sum is finite.
Finally partition the integers according to . For a fixed divisor of , writing leaves and , hence choices. Summing proves ; inversion gives the final formula.
Proof X-ray
Where the cancellation enters, and why the sign must ignore multiplicity
Only one identity in the inversion proof is not bookkeeping: the cancellation for . The rest is a change of the order of a finite sum. Substituting produces a sum over pairs of positive integers with ; grouping those pairs by instead of by leaves running over the divisors of . The cancellation identity, applied to rather than to , then deletes every except . The converse uses the same identity in the other grouping.
Nothing about or is assumed: no multiplicativity, positivity or growth condition is used, because every sum is finite. What is used is the exact choice of signs. If one replaced by the sign , where counts prime factors with multiplicity, then at the divisor sum of signs is , not . Taking and for , so that is constantly , the analogue of the inversion formula would return at instead of . Assigning zero to non-squarefree divisors is what makes the subset sum appear.
Worked examples
Worked example 4.1.4
(Three functions at one integer)
For , , , and . The formulas count different objects: number of divisors, sum of divisors, and number of units.
Worked example 4.1.5
(Inverting an observed divisor total)
Suppose and . At , only have nonzero Möbius values, so . More generally inversion gives by expanding over squarefree divisors.
Worked example 4.1.6
(Why multiplicative is weaker than completely multiplicative)
but , so . Likewise . These are not counterexamples to multiplicativity, because the factors are not coprime. In contrast, .
Divisors as independent exponent choices
The divisor formulas are useful because unique factorization converts a global question into independent local choices. For each prime dividing an integer, a divisor may use any exponent from zero up to the exponent in that integer. Once these exponents are chosen, there is exactly one divisor. Conversely every divisor yields exactly one such list. The formulas are therefore consequences of a bijection, rather than coincidences observed in numerical tables.
This viewpoint explains why the number-of-divisors formula multiplies counts whereas the sum-of-divisors formula multiplies sums. In the first case each exponent choice contributes a weight of one. In the second case a choice contributes the corresponding prime power, and the product of those local weights is the divisor itself. Expanding a product of sums enumerates every exponent tuple once with the correct weight. The same method applies whenever a multiplicative weight is assigned to divisors.
A perfect square provides a useful check. Its prime exponents are all even, so every factor in its divisor-count product is odd. Conversely, if the divisor count is odd, every exponent must be even. Hence a positive integer has an odd number of positive divisors exactly when it is a square. There is also a pairing proof: pair each divisor with the complementary divisor obtained by dividing the integer by it; only a square root can be paired with itself. Two different viewpoints reach the same conclusion and expose different aspects of the structure.
Multiplicativity is a restriction on coprime inputs
To use multiplicativity correctly, first separate prime powers belonging to different primes. One cannot generally split a prime power into repeated copies of its prime and multiply function values, because those factors are not coprime. A table of prime-power values is therefore the correct local data. A table of values only at primes would suffice for a completely multiplicative function, but not for a general multiplicative one.
For example, the function assigning an integer its number of divisors has value two at every prime. Those values alone do not tell us its value at a prime square; the definition and exponent enumeration give three, rather than four. In practical computations, writing the coprime factorization first prevents the wrong rule from slipping into the arithmetic. The distinction also matters in proofs: a product identity proved under a gcd condition cannot be applied again without checking that condition at the new inputs.
The Möbius function is a cancellation device
The Möbius function ignores divisors containing a repeated prime because its purpose is to organize subsets of the distinct prime factors. A squarefree divisor corresponds to choosing a subset of those primes. Its sign records whether the subset has even or odd size. Summing over subsets produces the same alternating cancellation as inclusion–exclusion. The definition may look irregular when listed as a sequence, but it is systematic when viewed on the divisor structure of one fixed integer.
This also proves that the Möbius function is multiplicative. If two inputs are coprime, their prime sets do not overlap. A repeated prime square occurs in their product exactly when it occurs in one of them; then both sides of the multiplicativity equation are zero. If neither has such a square factor, the numbers of selected distinct primes add, so their signs multiply. The value at one supplies the empty-set case. Thus the cancellation function fits the same local-to-global framework as the earlier divisor functions.
Convolution packages the inversion calculation
For arithmetic functions, define their divisor convolution at an integer by summing the value of the first at a divisor times the value of the second at the complementary divisor. There are only finitely many such factorizations. Exchanging a divisor with its complement shows this operation is commutative. Grouping triples of positive factors shows it is associative: either order of convolution sums the same weights over all triples whose product is the input.
The identity element for this operation is not the constant function one. It is the function that is one at the input one and zero elsewhere. Only the term with complementary factor one survives when convolving with it. The constant function one instead takes a function to its divisor sum. The Möbius cancellation identity says that the Möbius function is the convolution inverse of that constant function. Associativity then explains inversion in one sentence: applying the inverse undoes the divisor-sum operation.
Concept lensStructural
Inversion as undoing a finite aggregation
Divisor summation aggregates smaller contributions according to divisibility, rather than according to the usual order on integers. Möbius inversion is the inverse aggregation on this relation. The finite-sum proof remains essential: it verifies which pairs of divisors are being combined and why every unwanted contribution cancels.
This notation is optional for computation, but it is useful for recognizing the same pattern in new problems. It also gives a warning: convolution multiplication differs from pointwise multiplication. Multiplying two function values at the same input is not the same as summing over all factor pairs. A formula written with convolution must retain its meaning when translated back into ordinary sums.
A reconstruction procedure without symbolic inversion
The relation between a divisor total and its exact contribution is triangular. At input one the total equals the first contribution. At any larger input, subtract the already known contributions from all proper divisors to obtain the remaining contribution at the input itself. Since every proper positive divisor is smaller, this recursively determines the function. The argument proves uniqueness even without explicitly using the Möbius function.
Möbius inversion supplies a closed expression for that recursive subtraction. It therefore does not introduce additional assumptions about the unknown function: arbitrary complex-valued contributions are allowed, and no positivity is needed. A total can be positive while some individual contributions are negative. Such signs are not an error in the inversion; they depend on the actual data supplied. When the contributions count objects, a separate combinatorial interpretation may force nonnegativity, but that property comes from the interpretation rather than from the algebraic theorem alone.
The same triangular subtraction inverts sums over any partial order in which each element has finitely many predecessors.
A path to generalization
Inverting sums over other partial orders
The same triangular subtraction inverts sums over any partial order in which each element has finitely many predecessors.
The reconstruction used only that each input has finitely many divisors. On a partial order in which every set is finite, define and for . Then for all holds exactly when for all . For divisibility, ; for subsets of a finite set, , which is inclusion–exclusion.
Counting coprime numerators by exact denominator
The identity involving Euler's function can be read as reducing fractions to lowest terms. Start with the fractions whose numerator ranges from one through the fixed denominator. After reducing a fraction, its exact denominator is a divisor of the original denominator. For each possible exact denominator, the reduced numerators are precisely the integers in its range coprime to it. Partitioning by this exact denominator gives the divisor sum. This interpretation includes the endpoint fraction equal to one; the convention for Euler's function at one is what counts that case correctly.
The proof by gcd classification and the reduced-fraction interpretation describe the same partition in different language. Recognizing this link helps decide when inversion is appropriate: first identify a total that groups objects by a unique divisor-valued parameter, then recover the contribution for one exact value of that parameter.
A final useful check is that integer-valued totals recover integer-valued contributions: the inversion formula uses only integer coefficients and finitely many terms. This does not require positivity or any growth estimate. The value at one is checked first, then each larger input is recovered independently from its finite divisor set. Consequently this elementary inversion theorem is available even when no infinite generating series converges. Questions about asymptotic size require additional arguments beyond the finite algebra proved here.
Common mistakes
Common mistake
(A divisor sum includes both and )
A divisor sum runs over positive divisors, including and . Omitting breaks both inversion and the normalization at . For instance, summing only over the divisors of gives , not .
Common mistake
(The Möbius sign does not count repeated primes)
The Möbius value depends on repeated prime factors: , whereas . Counting the total number of prime factors with multiplicity and assigning a sign would give at and define a different function, whose divisor sums do not cancel.
Common mistake
(The inner sum runs over divisors of )
When rearranging the inversion sum, track the exact condition . The inner sum is over divisors of , not over divisors of independently of . This restriction is what isolates .
Summary
Unique factorization converts divisor enumeration into independent exponent choices. Möbius cancellation removes contributions from proper divisors, giving a reversible relation between exact contributions and their divisor totals.
Exercises
Quick check
(Compute , , , and .)
Factor first; do not enumerate candidates.
Solution · Answer
. Thus , , and . Since , .
Quick check
(Suppose the sum of over positive divisors of is for every . Determine and justify uniqueness.)
Use either inversion or the definition of .
Solution · Answer
The constant function has divisor sum , so it is a solution. Möbius inversion makes uniquely determined, so there is no other solution. Equivalently subtract two proposed solutions and induct on : all proper-divisor contributions vanish first, forcing the remaining contribution to vanish.
Quick check
(Suppose for every . Find and check the answer at with the inversion formula.)
Compare the definition of with the definition of a divisor sum.
Solution · Answer
By definition , so is a solution, and Möbius inversion shows it is the only one. At the divisors with nonzero Möbius value are , so the formula gives , as expected.