Algebraic Structure in Number Theory
In algorithm design, problems involving greatest common divisors ($\gcd$), coprime pairs, and divisor sums routinely appear to require quadratic $O(N^2)$ enumeration. Reducing them to $O(N \log N)$ or $O(N)$ relies on treating arithmetic functions not as isolated formulas, but as elements of an algebraic ring equipped with Dirichlet convolution.
Let’s develop this algebra from first principles, derive the Möbius inversion theorem and the coprimality indicator identity, and implement Euler’s $O(N)$ linear sieve in modern C++20.
1. Multiplicative Arithmetic Functions
An arithmetic function is any mapping $f : \mathbb{Z}_{\ge 1} \to \mathbb{C}$. We say that $f$ is multiplicative if $f(1) = 1$ and, for all coprime integers $a, b$ ($\gcd(a, b) = 1$):
$$f(ab) = f(a),f(b).$$
By the Fundamental Theorem of Arithmetic, every integer $n > 1$ has a canonical prime factorization $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$. Because distinct prime powers $p_i^{e_i}$ are pairwise coprime, a multiplicative function is completely determined by its values on prime powers:
$$f(n) = \prod_{i=1}^k f!\left(p_i^{e_i}\right).$$
Core Multiplicative Functions
| Symbol | Name | Definition on $n$ | Value on Prime Power $p^e$ ($e \ge 1$) |
|---|---|---|---|
| $\varepsilon(n)$ | Dirichlet Unit | $[n = 1]$ ($1$ if $n=1$, else $0$) | $0$ |
| $\mathbf{1}(n)$ | Constant Unit | $1$ for all $n \ge 1$ | $1$ |
| $\text{id}(n)$ | Identity | $n$ | $p^e$ |
| $\tau(n)$ | Divisor Count | $\sum_{d \mid n} 1$ | $e + 1$ |
| $\varphi(n)$ | Euler’s Totient | $\bigl\vert{1 \le k \le n : \gcd(k, n) = 1}\bigr\vert$ | $p^{e-1}(p - 1)$ |
| $\mu(n)$ | Möbius Function | $(-1)^k$ if $n = p_1\cdots p_k$ is square-free; $0$ if $p^2 \mid n$ | $-1$ if $e = 1$; $;0$ if $e \ge 2$ |
2. The Dirichlet Convolution Group and Möbius Inversion
Given two arithmetic functions $f$ and $g$, their Dirichlet convolution $f * g$ is defined by summing over all divisor pairs multiplying to $n$:
$$(f * g)(n) = \sum_{d \mid n} f(d),g!\left(\frac{n}{d}\right) = \sum_{ab = n} f(a),g(b).$$
Dirichlet convolution is commutative ($f * g = g * f$), associative ($(f * g) * h = f * (g * h)$), and has $\varepsilon(n) = [n = 1]$ as its identity element:
$$(f * \varepsilon)(n) = \sum_{d \mid n} f(d),\left[\frac{n}{d} = 1\right] = f(n).$$
Moreover, the convolution of two multiplicative functions is multiplicative.
Lemma (The Fundamental Möbius Identity: $\mu * \mathbf{1} = \varepsilon$)
For every integer $n \ge 1$:
$$\sum_{d \mid n} \mu(d) = [n = 1] = \varepsilon(n).$$
Proof. Let $h = \mu * \mathbf{1}$. Since both $\mu$ and $\mathbf{1}$ are multiplicative, $h$ is multiplicative, so it suffices to evaluate $h(1)$ and $h(p^e)$ for prime powers $p^e$ ($e \ge 1$):
- $h(1) = \mu(1) = 1 = \varepsilon(1)$.
- For $e \ge 1$, since $\mu(p^j) = 0$ for all $j \ge 2$: $$h(p^e) = \sum_{j=0}^e \mu(p^j) = \mu(1) + \mu(p) + 0 + \dots + 0 = 1 + (-1) = 0 = \varepsilon(p^e).$$
By multiplicativity, $h(n) = \prod_i h(p_i^{e_i}) = \varepsilon(n)$ for all $n \ge 1$. $\square$
Theorem (Möbius Inversion)
In the Dirichlet ring, $\mu$ is the exact inverse of the constant function $\mathbf{1}$. Therefore, for any arithmetic functions $f$ and $g$:
$$g(n) = \sum_{d \mid n} f(d) \quad \Longleftrightarrow \quad g = f * \mathbf{1} \quad \Longleftrightarrow \quad f = g * \mu \quad \Longleftrightarrow \quad f(n) = \sum_{d \mid n} \mu(d),g!\left(\frac{n}{d}\right).$$
(As an immediate corollary, since $\sum_{d \mid n} \varphi(d) = n$, we have $\varphi * \mathbf{1} = \text{id}$, which inverts to $\varphi = \text{id} * \mu$, i.e., $\varphi(n) = \sum_{d \mid n} \mu(d)\frac{n}{d}$).
The Coprimality Indicator Trick
Substituting $n = \gcd(x, y)$ into the fundamental identity $\sum_{d \mid n} \mu(d) = [n = 1]$ yields the workhorse identity of algorithmic number theory:
$$[\gcd(x, y) = 1] = \sum_{d \mid \gcd(x, y)} \mu(d) = \sum_{\substack{d \mid x \ d \mid y}} \mu(d).$$
Why is this identity so effective? Because $d \mid \gcd(x, y) \iff (d \mid x \text{ and } d \mid y)$. This decouples a pairwise condition between $x$ and $y$ into independent divisibility events over common divisors $d$, allowing us to swap sums and count coprime pairs across an entire array in $O(M \log M)$ time instead of $O(N^2)$.
3. Euler’s $O(N)$ Linear Sieve
The classical Sieve of Eratosthenes marks multiples of every prime $p \le N$, visiting a number with $k$ distinct prime factors $k$ times for an asymptotic runtime of $\sum_{p \le N} \frac{N}{p} = \Theta(N \log \log N)$.
Euler’s Linear Sieve achieves strict $O(N)$ time—and simultaneously computes any multiplicative function ($\mu$, $\varphi$, $\text{spf}$)—by enforcing a single structural invariant:
Every composite integer $x$ is crossed out exactly once, by its smallest prime factor $p = \text{spf}(x)$, written as $x = p \cdot i$ where $p \le \text{spf}(i)$.
For each integer $i$ from $2$ to $N$, we iterate through the list of already-discovered primes $p$:
- Case 1 ($p < \text{spf}(i)$, so $p \nmid i$): Because $p$ does not divide $i$, $\gcd(p, i) = 1$. Any multiplicative function satisfies $f(i \cdot p) = f(i),f(p)$: $$\mu(i \cdot p) = -\mu(i), \qquad \varphi(i \cdot p) = \varphi(i),(p - 1).$$
- Case 2 ($p = \text{spf}(i)$, so $p \mid i$): Now $p^2 \mid (i \cdot p)$, meaning $i \cdot p$ is not square-free:
$$\mu(i \cdot p) = 0, \qquad \varphi(i \cdot p) = \varphi(i) \cdot p.$$
Crucially, we
breakout of the prime loop immediately. Why? Because for any larger prime $q > p$, the composite $y = i \cdot q$ has smallest prime factor $p$ (since $p \mid i \implies p \mid y$ and $p < q$). Breaking ensures $y$ is not touched now; it will be visited uniquely later when the outer loop reaches $i’ = (i / p) \cdot q$.
Idiomatic C++20 Implementation
| |
Notice the helper method squarefree_divisors(x): because any divisor $d$ with $p^2 \mid d$ has $\mu(d) = 0$, Möbius sums $\sum_{d \mid x} \mu(d),C[d]$ only ever need the $2^{\omega(x)}$ square-free divisors of $x$. For $x \le 10^6$, an integer has at most $\omega(x) \le 7$ distinct prime factors ($2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = 510{,}510$), meaning squarefree_divisors(x) returns at most $2^7 = 128$ integers and is extracted in $O(\log x)$ prime-factor division steps.