Arithmetic & Multiplicative Functions Explained

An arithmetic function is simply a function whose input is a positive integer — examples are φ(n), the count of numbers below n coprime to n, or d(n), the number of divisors of n. A multiplicative function is a special arithmetic function with a powerful property: whenever m and n share no common factor, f(m·n) = f(m)·f(n). This means the whole function is determined by its values on prime powers, which makes it far easier to compute and analyse.

These functions matter because they package deep facts about integers into neat formulas. The Möbius function detects square factors, the Euler totient counts usable residues for cryptography, and the divisor functions classify perfect numbers. Their Dirichlet convolution turns number-theoretic relationships into algebra, and Möbius inversion — the flagship result — lets you recover a function from its divisor sums.

Key Concepts

• Arithmetic function: any function f: N → C defined on the positive integers.
• Multiplicative: f(mn) = f(m)f(n) whenever gcd(m, n) = 1; determined by values f(p^a) on prime powers.
• Completely multiplicative: f(mn) = f(m)f(n) for all m, n, e.g. f(n) = n^k.
• Euler totient φ(n): counts integers 1 ≤ k ≤ n coprime to n; the classic multiplicative function.
• Divisor functions: τ(n) (also d(n)) counts divisors; σ(n) sums them; both multiplicative.
• Möbius function μ(n): 0 if n has a squared prime factor, otherwise (−1)^k where k is the number of distinct prime factors.
• Dirichlet convolution: (f ∗ g)(n) = Σ f(d)·g(n/d) over all divisors d of n; the convolution of multiplicative functions is multiplicative.

Formulas

• Euler totient: φ(n) = n·∏(1 − 1/p) over the distinct primes p dividing n.
• Divisor count: for n = ∏ p_i^a_i, τ(n) = ∏(a_i + 1).
• Divisor sum: σ(n) = ∏ (p_i^a_i+1 − 1)/(p_i − 1).
• Möbius inversion: if F(n) = Σ f(d) over d | n, then f(n) = Σ μ(d)·F(n/d) over d | n.
• Key identity: Σ μ(d) over d | n equals 1 if n = 1 and 0 otherwise; Σ φ(d) over d | n equals n.
• Multiplicativity test: f is multiplicative ⟺ f(∏ p_i^a_i) = ∏ f(p_i^a_i).

Worked Example

Compute φ(12), τ(12) and σ(12). Step 1: factorise 12 = 2^2·3. Step 2: φ(12) = 12·(1 − 1/2)·(1 − 1/3) = 12·(1/2)·(2/3) = 4. Verification: the numbers from 1 to 12 coprime to 12 are 1, 5, 7, 11 — exactly 4 ✓. Step 3: τ(12) = (2 + 1)·(1 + 1) = 6. Verification: the divisors are 1, 2, 3, 4, 6, 12 — exactly 6 ✓. Step 4: σ(12) = ((2^3 − 1)/(2 − 1))·((3^2 − 1)/(3 − 1)) = (7/1)·(8/2) = 7·4 = 28. Verification by direct addition: 1 + 2 + 3 + 4 + 6 + 12 = 28 ✓. Bonus check of the identity Σ φ(d) = n: the divisors of 12 are 1, 2, 3, 4, 6, 12 with φ-values 1, 1, 2, 2, 2, 4, and 1 + 1 + 2 + 2 + 2 + 4 = 12 ✓.

Common Misconceptions

• "Multiplicative means f(mn) = f(m)f(n) for all m and n." That stronger property is called completely multiplicative. Ordinary multiplicativity only requires the identity when m and n are coprime — φ and σ satisfy this but are not completely multiplicative.
• "μ(n) = 0 means n is not squarefree." That is correct, but students often flip it: μ(n) = ±1 exactly when n is squarefree. Remember that μ(1) = 1, not 0.
• "Dirichlet convolution is just pointwise multiplication." No: (f ∗ g)(n) sums over divisor pairs of n, not over the single value n. It behaves like multiplication of Dirichlet series, which is why Möbius inversion works.

Real-World Applications

• RSA cryptography: key generation computes φ(n) = (p − 1)(q − 1) for n = pq, using the totient's multiplicativity on coprime factors.
• Signal processing: Möbius inversion over divisor lattices appears in algorithms that untangle periodic signals.
• Counting problems: φ counts reduced fractions with a given denominator, which underlies Farey sequences and rational approximation.
• Analytic number theory: summatory functions of μ and Λ are directly tied to the distribution of primes and the Riemann hypothesis.

Arithmetic functions organise facts about integers, and multiplicativity is the property that makes them computable from prime factorisations. The totient, divisor-count and divisor-sum formulas all flow from evaluating the function on prime powers and multiplying, while Möbius inversion lets you move between a function and its divisor sums. Master these, and you hold the algebraic toolkit behind prime counting, perfect numbers and modern cryptography.