Sometimes the quickest way to count integers is to stop examining them one at a time and count their divisibility patterns instead. Arithmetic functions record those patterns. The totient counts coprime residues, the divisor functions count and sum factors, and the Möbius function supplies the alternating signs needed to undo overcounting.
The resulting algorithms connect familiar factors and multiples to much larger computations. We can count coprime pairs without running a gcd for every pair, count square-free integers without independently factoring every integer, and recover a function from sums over its divisors. The same inversion even counts irreducible polynomials over a finite field.
This is Guide 12 in the Bukit Timah Tutor Computational Number Theory series. It completes a batch connecting finite fields, polynomial factorisation, prime-power precision and divisor-based counting. Basic divisibility, prime factorisation and sums are enough to begin. Use the BTT Mathematics Hub for the wider learning route.
1. An arithmetic function has an integer argument
An arithmetic function assigns a value to each positive integer. The value might count something about the integer, record a sign or describe its factorisation. The word arithmetic here identifies the domain and subject matter; it does not mean that every arithmetic function is linear or easy to compute.
Examples include φ(n), the number of integers from one through n that are coprime to n; τ(n), the number of positive divisors; and σ(n), the sum of positive divisors. We use τ for the divisor count to avoid confusing the function with a summation variable d. NIST’s number-theory chapter gives these standard definitions and conventions. [1]
For n=12, the coprime residues are 1,5,7,11, so φ(12)=4. The divisors are 1,2,3,4,6,12, so τ(12)=6 and σ(12)=28. These are three different summaries of the same integer.
The value at one matters. Its only positive divisor is one, and gcd(1,1)=1, so φ(1)=τ(1)=σ(1)=1. These conventions make the later product and inversion identities work at the boundary instead of requiring repeated exceptions.
2. Multiplicative is not completely multiplicative
A function f with f(1)=1 is multiplicative when f(ab)=f(a)f(b) whenever gcd(a,b)=1. It is completely multiplicative when the identity holds without the coprimality restriction. The distinction is essential; the standard totient and divisor functions are multiplicative but not generally completely multiplicative. [2]
For example, τ(2)=2 but τ(4)=3, not four. The two copies of the prime two overlap, so their divisor choices cannot be treated as independent. However, τ(3·4)=τ(3)τ(4)=2·3=6 because three and four are coprime.
The condition tells us how to exploit a prime factorisation. Distinct prime powers are coprime, so a multiplicative function is determined by its values on prime powers. There is no need to assert multiplicativity across overlapping factors.
A good implementation test therefore includes both coprime and noncoprime pairs. Checking only examples such as 3·5 can hide the mistaken assumption that every product should factor through the function.
3. Divisor counts and sums from prime powers
If n=p1^a1·…·pr^ar, every divisor chooses an exponent from zero through ai for each prime pi. The choices are independent because distinct primes have unique exponents in a factorisation. Thus τ(n)=∏(ai+1).
The divisor sum uses the same choices but weights each by its divisor value. For a prime power p^a, the sum is 1+p+…+p^a. Multiplying these geometric sums generates each divisor exactly once, so σ(n)=∏(1+pi+…+pi^ai).
Take n=36=2²·3². There are three choices for each exponent, giving τ(36)=9. The sum is (1+2+4)(1+3+9)=7·13=91. The nine actual divisors provide a direct verification: 1,2,3,4,6,9,12,18,36.
The formula saves enumeration once the factorisation is known. It does not make factorisation free. For a single huge input whose factors are unknown, the cost of obtaining those factors belongs to the overall computation and must not be omitted from a running-time claim.
4. Euler’s totient from exclusion
For p prime, among the integers one through p^a, exactly p^(a−1) are multiples of p. All the others are coprime to p^a. Therefore φ(p^a)=p^a−p^(a−1).
For a general n, exclude multiples of each distinct prime divisor by inclusion–exclusion. The result is φ(n)=n∏(1−1/p), with the product taken over distinct primes dividing n. The standard multiplicative formulas are recorded in NIST’s treatment. [2]
For 36, exclude divisibility by two and three: φ(36)=36·(1/2)·(2/3)=12. For 30, the distinct primes are two, three and five, giving φ(30)=30·(1/2)·(2/3)·(4/5)=8.
Each distinct prime enters once even when its exponent in n is larger. That is why the formula for 36 does not include the factors for two and three twice. Their repeated powers affect the initial size n, not the number of separate exclusion conditions.
5. The Möbius function records square-free signs
The Möbius function μ(n) is one at n=1, zero when a prime square divides n, and (−1)^r when n is a product of r distinct primes. It is a sign-valued arithmetic function with zeros that suppress repeated prime factors. [1]
Thus μ(6)=1, μ(30)=−1, μ(36)=0 and μ(210)=1. The relevant count is the number of distinct primes only after square-freeness has been checked. Counting four prime factors with multiplicity in 36 and returning a positive sign would be wrong.
An integer is square-free when no prime square divides it. One is square-free under this definition. A square-free integer may have many distinct prime divisors; the word square-free does not mean prime or free of all factors.
The function is multiplicative. For coprime a and b, a repeated prime square occurs in their product exactly when one already occurs in a factor; otherwise the numbers of distinct primes add and the signs multiply. The coprimality condition again prevents hidden overlap.
6. The cancellation identity behind inversion
The crucial identity is Σ(d divides n) μ(d)=1 when n=1 and zero otherwise. It is the divisor-sum cancellation that makes Möbius inversion possible. [3]
To prove it, let n have r distinct prime divisors. Divisors containing a squared prime contribute zero. The remaining divisors correspond to subsets of the r primes, with sign (−1) raised to the subset size. Their sum is (1−1)^r.
For n>1, r is positive and the sum vanishes. For n=1, the empty subset contributes one. This proof explains both the alternating sign and the special value at one; neither is an arbitrary convention added after the fact.
For n=12, the divisors are 1,2,3,4,6,12. The corresponding Möbius values are 1,−1,−1,0,1,0, which sum to zero. The repeated prime in four and twelve contributes nothing, while the square-free divisors perform the cancellation.
7. Dirichlet convolution organises divisor sums
For arithmetic functions f and g, their Dirichlet convolution is (f*g)(n)=Σ(d divides n) f(d)g(n/d). This operation is commutative and associative under the usual scalar arithmetic. Its identity is ε, with ε(1)=1 and ε(n)=0 for n>1—not the constant-one function. [3]
Let 1 denote the constant-one function, and let id(n)=n. Then τ=1*1 because every divisor contributes one. Also σ=1*id because the complementary divisors n/d run through the same divisor set as d.
The Möbius cancellation identity becomes μ*1=ε. This says that μ is the convolution inverse of the constant-one function. It does not say that μ(n)=1/1 pointwise. Convolution is a different multiplication operation on functions.
That distinction can feel abstract until it is used. A divisor sum is multiplication by the function 1 under convolution. Undoing the divisor sum therefore means multiplying by μ under the same operation. The notation compresses a real cancellation mechanism.
8. Möbius inversion, derived rather than memorised
Suppose F(n)=Σ(d divides n) f(d). Then f(n)=Σ(d divides n) μ(d)F(n/d). This is the divisor form of Möbius inversion. The functions need not be multiplicative; the finite sum identity itself is more general. [3]
Expand the proposed inverse: Σ(d|n) μ(d)Σ(e|n/d) f(e). Collect terms with the same e. The coefficient of f(e) is Σ(d|n/e) μ(d). By the cancellation identity, this coefficient is zero unless e=n, when it is one.
Every unwanted divisor contribution cancels. Only f(n) remains. This proof is short, but it contains the entire algorithmic idea: the signs do not estimate or approximately correct the total; they remove the overlap exactly.
For a small numerical example, let f(n)=n. Then F=σ. At n=12, inversion gives f(12)=σ(12)−σ(6)−σ(4)+σ(2)=28−12−7+3=12. The omitted divisors have Möbius value zero.
9. Recovering the totient through inversion
The identity Σ(d divides n) φ(d)=n has a direct counting proof. Partition the integers k from one through n according to gcd(k,n)=g. Dividing k and n by g shows that the class has φ(n/g) elements. Summing over all divisors g counts all n integers.
Apply Möbius inversion to get φ(n)=Σ(d divides n) μ(d)·n/d. This is the same totient encoded as a divisor sum rather than a prime product. NIST lists the two paired identities explicitly. [4]
At n=12, the nonzero contributions are 12−6−4+2=4. The answer agrees with the four coprime residues and with the prime-factor formula. These are three representations of one count, useful for independent verification.
The identity also suggests a table-building algorithm. If smaller totients are already known, subtract them from n to recover φ(n). A prime-based sieve is usually more economical, but the divisor recurrence is valuable because its correctness follows directly from the count.
10. Build a totient table by sieving
Suppose the task is to compute φ(n) for every n up to N. Factoring every n independently repeats much of the same divisibility work. Instead, initialise φ[k]=k and process each prime p across all its multiples.
At each multiple k of p, update φ[k] by subtracting φ[k]/p. The division is exact at that stage. A prime p has not been modified by any smaller prime, so φ[p]=p identifies it during this particular sieve.
phi[k] = k for k=0,…,N
for p=2,…,N:
if phi[p] == p:
for k=p,2p,3p,… up to N:
phi[k] -= phi[k]/p
Each prime acts once on each relevant integer, implementing the product formula through exact integer updates. For k=12, the initial value twelve becomes six after processing two, then four after processing three.
The number of updates is governed by the sum of N/p over primes up to N. In the usual arithmetic-operation model this gives the familiar O(N log log N) sieve scale. The array uses O(N) entries; the bit cost and language-level object overhead are separate considerations.
11. Build a Möbius table alongside it
Start μ[k]=1 for positive k. For every prime p, change the sign at every multiple of p. Then set μ[k]=0 at every multiple of p². The sign counts distinct prime divisors, while the square pass removes integers that are not square-free.
Once an entry is zero, later sign changes leave it zero. Therefore processing the primes in increasing order does not require a special recovery rule for entries already known to have repeated prime factors.
The combined teaching implementation below uses the totient sieve’s prime detection. It returns both tables and deliberately defines array entry zero only as a storage convention; the arithmetic functions in this guide are defined on positive integers.
def arithmetic_tables(n: int):
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer.")
phi = list(range(n + 1))
mu = [1] * (n + 1)
mu[0] = 0
for p in range(2, n + 1):
if phi[p] == p:
for k in range(p, n + 1, p):
phi[k] -= phi[k] // p
mu[k] *= -1
for k in range(p * p, n + 1, p * p):
mu[k] = 0
return phi, mu
phi, mu = arithmetic_tables(36)
assert phi[1] == 1 and mu[1] == 1
assert phi[12] == 4
assert phi[36] == 12
assert mu[30] == -1
assert mu[36] == 0The square-marking work adds a sum of roughly N/p² updates over primes, which does not change the leading sieve scale. The code prioritises visible logic over memory compression. It is intended for manageable classroom bounds, not as a universal large-N implementation.
12. Read the first ten values as a diagnostic table
n: 1 2 3 4 5 6 7 8 9 10 phi: 1 1 2 2 4 2 6 4 6 4 mu: 1 -1 -1 0 -1 1 -1 0 0 1
The zero Möbius entries at four, eight and nine expose squared prime divisors. The positive values at six and ten record products of two distinct primes. The value at one is not an exception to be patched later; it is required by convolution inversion.
A useful test compares the totient table with direct gcd counting for small n. For μ, compare with trial factorisation, then check that the divisor sum is zero at every n>1. The two tests examine different aspects: one checks individual values, the other checks a global identity among them.
The displayed sieve was checked against direct counts and reference arithmetic for n from one through 300. The table identities were also checked over that range. This is bounded implementation evidence, not a claim that testing finitely many n proves an unbounded algorithm correct.
13. Count coprime pairs without a quadratic gcd loop
Let C(N) count ordered pairs (a,b) with 1≤a,b≤N and gcd(a,b)=1. A direct algorithm computes N² gcds. Möbius inversion gives a different route.
The indicator of coprimality is Σ(d divides gcd(a,b)) μ(d). It equals one when the gcd is one and zero otherwise. Sum that indicator over all pairs and reverse the order of summation. For a fixed d, both coordinates must be multiples of d, giving floor(N/d)² pairs.
C(N) = Σ from d=1 to N of μ(d)·floor(N/d)².
This is an exact finite identity. It does not assume that divisibility events are independent. The alternating Möbius signs account for the overlaps among prime-divisibility conditions.
The reduction changes the workload from a pair-by-pair gcd calculation to a single weighted sum once the Möbius table is available. Whether that is worthwhile for a particular small N depends on setup cost, but the structural advantage becomes clear as the number of queried pairs grows.
14. A complete coprime count for a ten-by-ten grid
For N=10, use the first ten Möbius values. The nonzero terms are 100−25−9−4+1−1+1=63. Thus exactly 63 of the 100 ordered positive-coordinate pairs are coprime.
There is an independent totient check. Above the diagonal, for each b from two through ten, there are φ(b) choices of a with 1≤a<b and gcd(a,b)=1. The same number occurs below the diagonal, while only (1,1) on the diagonal is coprime.
C(N) = 1+2·Σ from b=2 to N of φ(b). C(10) = 1+2·31 = 63.
The grid count has a geometric interpretation: a positive integer point is visible from the origin exactly when its coordinates are coprime. If they share a divisor d>1, the line segment contains a nearer integer point. This statement concerns the positive grid defined here; including axes or signed coordinates changes the counting conventions.
The finite fraction 63/100 is the exact answer for this grid. It should not be replaced by an asymptotic density or presented as the probability for every possible range.
15. Square-free counting from squared divisors
The indicator that n is square-free is Σ(d² divides n) μ(d). If a prime square divides n, the square-divisor contributions cancel; otherwise only d=1 contributes. This is another application of the same subset-sign mechanism.
Summing up to N and swapping the order gives an exact count Q(N):
Q(N) = Σ from d=1 to floor(sqrt(N))
of μ(d)·floor(N/d²).
Only d up to sqrt(N) are needed because no larger positive square can divide an integer at most N. This gives a much smaller Möbius-table requirement than the coprime-grid count.
For N=50, the terms are 50−12−5−2+1−1=31. The omitted d=4 term is zero. Therefore there are exactly 31 square-free positive integers up to fifty, including one.
Again, the method counts overlap correctly. Simply subtracting the counts of multiples of four, nine, twenty-five and forty-nine would subtract some integers more than once. The positive term for d=6 restores the overlap from divisibility by 2² and 3².
16. A divisor sum can replace many gcd values
The identity Σ(d divides n) φ(d)=n can be applied to a gcd itself. For any positive a,b, gcd(a,b)=Σ(d divides both a and b) φ(d). Summing over a positive N-by-N grid gives:
Σ over 1≤a,b≤N of gcd(a,b) = Σ from d=1 to N of φ(d)·floor(N/d)².
The structure is nearly identical to the coprime count, but the weight has changed from μ to φ. One weight selects gcd equal to one; the other reconstructs the gcd’s numerical value from its divisor classes.
For N=3, the right side is 1·9+1·1+2·1=12. Directly summing the nine gcds gives the same answer. This small example is useful because every term is visible and no performance claim is needed to understand the transformation.
These identities suggest a general question: can the quantity being summed be represented as a divisor sum? If so, reversing the order may turn a large two-dimensional enumeration into a much smaller collection of divisibility counts.
17. Group equal floor quotients
In sums involving floor(N/d), many consecutive d produce the same quotient. Suppose a block begins at l and v=floor(N/l). The largest r with the same quotient is floor(N/v). Every d from l through r contributes that same v.
For N=10, the quotient blocks are d=1 with value ten; d=2 with value five; d=3 with value three; d=4,5 with value two; and d=6,…,10 with value one.
Σ floor(10/d) = 10+5+3+2·2+5·1 = 27.
The general block loop advances l to r+1. There are only O(sqrt(N)) distinct quotients: values arising from small d are few, and the quotients themselves are small once d exceeds sqrt(N). This reduces the number of groups that must be processed.
For a weighted sum, use prefix sums of the weights. A block contribution to the coprime count is v²·(M(r)−M(l−1)), where M(t)=Σ(d≤t) μ(d). The large loop becomes a sequence of exact block contributions.
18. Quotient grouping does not erase preprocessing cost
It would be misleading to call the complete coprime-count procedure O(sqrt(N)) merely because the final grouped sum has that many blocks. If M(t) was prepared by sieving all values through N, the preprocessing still costs time and O(N) storage.
For many queries sharing the same upper bound, that preprocessing can be amortised. For one isolated huge N, a full table may be the dominant expense. More advanced summatory-function algorithms address that different problem, but they are not automatically supplied by a floor-block loop.
A meaningful complexity statement therefore identifies the stage: table construction, prefix-sum construction, one query, or many queries. The mathematical identity may be the same while the computational accounting changes.
The same warning applies to the square-free count. Its simple formula only requires μ through sqrt(N), but computing those values and storing them still belongs in the total cost. Honest accounting is part of computational Mathematics.
19. Direct divisor transforms for arbitrary data
Möbius inversion is not limited to familiar named functions. Suppose a table f[1…N] contains arbitrary integer values and F[n] is the sum of f[d] over divisors d of n. The forward transform can be computed by adding f[d] to every multiple of d.
F[1…N] = 0
for d=1,…,N:
for multiple=d,2d,3d,… up to N:
F[multiple] += f[d]
The number of visits is Σ(d≤N) floor(N/d), which has the familiar O(N log N) scale. This is a direct divisor transform, not a prime sieve. Calling both procedures a sieve without stating their loops can conceal a different complexity.
The inverse can be computed by the Möbius formula or by triangular elimination. Copy F into a working array. Process d in increasing order; its current entry is f[d], and subtract it from every proper multiple of d. All smaller-divisor contributions have already been removed when d is reached.
The two inverse methods provide an independent correctness check. Their equality is a theorem, but distinct implementations can still disagree because of an off-by-one error, an incorrect initial value or the accidental inclusion of zero as a divisor.
20. Counting irreducible polynomials
Let I_q(n) be the number of monic irreducible degree-n polynomials over Fq. The finite-field factorisation theorem says that X^(q^n)−X contains exactly the irreducibles whose degrees divide n. Taking degrees gives q^n=Σ(d divides n) d·I_q(d). [5]
Now apply Möbius inversion to the arithmetic function n·I_q(n). The result is:
I_q(n) = (1/n)·Σ over d dividing n of μ(d)·q^(n/d).
This connects divisor inversion to the previous polynomial-factorisation guide. The exponents in the finite-field theorem become divisor arguments in an arithmetic function. No numerical approximation is involved.
For q=2 and n=6, the count is (64−8−4+2)/6=9. For n=4 it is (16−4)/4=3. The division by n produces an integer because the expression counts monic irreducibles; exact divisibility is an excellent implementation check.
The formula counts polynomials, not primitive elements and not field isomorphism classes. There is one field of a given prime-power size up to isomorphism, but many possible irreducible defining polynomials. Counting these different objects under one label would give incompatible answers.
21. How to choose the computational route
For one integer whose prime factorisation is already known, use prime-power formulas. For every value up to a moderate bound, use a sieve. For arbitrary divisor-aggregated data, use a divisor transform and its inverse. For coprime or gcd-weighted pair counts, search for an indicator or divisor identity before committing to a quadratic enumeration.
For square-free counting up to N, the direct Möbius formula only needs a table to sqrt(N). For polynomial counts I_q(n), only divisors of n appear, but exact powers q^(n/d) may be large. The output size and arithmetic cost remain part of the calculation.
Do not introduce a sophisticated method merely because its name is advanced. A ten-by-ten grid can be enumerated directly for verification. A million repeated gcd queries may benefit from a transformed sum. The correct tool follows the actual workload.
Good implementations also return enough context to interpret the result: whether pairs are ordered, whether zero or negative coordinates are included, whether one is counted as square-free, and whether polynomial factors are monic. These are mathematical choices, not incidental formatting.
22. Common failure patterns
The first failure is dropping coprimality from a multiplicative identity. The second is confusing convolution with pointwise multiplication. The third is using the constant-one function where the convolution identity ε is required. Each produces plausible-looking formulas that fail on small counterexamples.
A fourth failure is losing the square-free condition in μ. A fifth is treating a failed sieve test as a definition rather than checking the prime-detection invariant of the particular algorithm. A sixth is claiming a grouped query cost while omitting the array construction that made it possible.
A seventh failure is changing the counting universe. Ordered pairs differ from unordered pairs; positive grids differ from grids including axes; polynomial counts differ from root counts. The final number can be arithmetically correct for the wrong set.
Use small independent examples to distinguish these failures. The values at one, prime squares, products of two distinct primes and a small exact grid are not trivial afterthoughts. They are concentrated tests of the definitions and boundaries.
23. Practice set
1. Find φ(36), τ(36), σ(36) and μ(36). 2. Find μ(30) and μ(210). 3. Give a counterexample showing that τ is not completely multiplicative. 4. Verify Σ(d|12) μ(d)=0.
5. Define the identity for Dirichlet convolution. 6. Recover f(12) from F(n)=σ(n) using Möbius inversion. 7. Compute φ(12) using the Möbius divisor formula. 8. Explain why a totient sieve processes each distinct prime once.
9. List μ(1) through μ(10). 10. Count ordered coprime pairs with coordinates from one to ten. 11. Check that count using totients. 12. Count square-free positive integers up to fifty.
13. Compute the sum of gcd(a,b) over the three-by-three positive grid. 14. Group the sum of floor(10/d) by equal quotient. 15. Explain why quotient grouping does not make a full Möbius-table construction sublinear. 16. Count monic irreducible degree-six polynomials over F2. 17. State one difference between a prime sieve and a divisor transform. 18. Explain why these counting formulas require no independence assumption.
24. Answers and worked checks
1. Since 36=2²·3², the values are φ=12, τ=9, σ=91 and μ=0. 2. Thirty is a product of three distinct primes, giving −1; 210 has four, giving +1. 3. τ(2)τ(2)=4 while τ(4)=3.
4. The divisor contributions are 1−1−1+0+1+0=0. 5. ε(1)=1 and ε(n)=0 for n>1. It differs from the constant-one function. 6. The answer is σ(12)−σ(6)−σ(4)+σ(2)=28−12−7+3=12.
7. φ(12)=12−6−4+2=4. 8. Coprimality excludes divisibility by each distinct prime; repeated powers are already reflected in n and do not create an additional independent exclusion condition.
9. The values are 1,−1,−1,0,−1,1,−1,0,0,1. 10. The weighted sum is 100−25−9−4+1−1+1=63. 11. The totients from two through ten sum to 31, so 1+2·31=63.
12. The squared-divisor sum is 50−12−5−2+1−1=31, including one. 13. The answer is 9·φ(1)+φ(2)+φ(3)=9+1+2=12. 14. The blocks contribute 10+5+3+4+5=27.
15. The prefix sums used in a grouped query still have to be obtained. A full sieve to N uses N-scale storage and preprocessing even when one later query has only square-root-scale groups. 16. I2(6)=(64−8−4+2)/6=9.
17. A prime sieve iterates over primes and their multiples; the direct divisor transform iterates over every positive divisor index and its multiples. Their visit counts differ. 18. Möbius signs perform exact inclusion–exclusion over divisor overlaps, so no probabilistic independence approximation is used.
25. The connected mathematical picture
The four guides in this batch share a method: choose a representation that exposes the structure the computation needs. Finite fields use polynomial remainders. Factorisation uses Frobenius and gcds. Hensel lifting uses precision digits and derivative corrections. Möbius inversion uses divisibility classes and cancellation.
None of these methods merely asks a computer to repeat school arithmetic faster. Each changes the shape of the problem while preserving the required mathematical relation. The gain comes from understanding what can be transformed without losing the answer.
Verification closes the process. Multiply factors back. Substitute a lifted root into the original polynomial. Check an inverse product. Recount a small grid independently. A result becomes usable when its meaning, assumptions and check are carried with it.
Sources and further study
[1] NIST Digital Library of Mathematical Functions, Functions of Number Theory: definitions. [2] NIST DLMF, Multiplicative Properties. [3] NIST DLMF, Inversion Formulas. [4] NIST DLMF, Divisor Sums. [5] Victor Shoup, A Computational Introduction to Number Theory and Algebra, Chapter 19, for finite-field polynomial counting. The sieve and finite counting examples are explicit worked constructions with the counting conventions stated in the text.
Computational Number Theory — Batch 03
Guide 9: Finite Fields, Polynomial Arithmetic and Exact Computation builds the arithmetic setting. Guide 10: Polynomial Factorisation over Finite Fields separates irreducible structure. Guide 11: p-Adic Valuations, Hensel Lifting and Prime-Power Precision refines local roots. This guide supplies divisor transforms, exact counts and their implementation checks.