How Mobius Function and Inversion Works: Implementation Guide

1. Introduction and Core Concepts

The Möbius function and Möbius inversion are among the most elegant and powerful tools in analytic number theory and combinatorics. Named after the German mathematician August Ferdinand Möbius, these concepts provide a systematic way to invert summations over divisors, transforming a function defined by its divisor sums back into its original form. At its heart, this is a principle of inclusion-exclusion encoded in an arithmetic function.

The Möbius function, denoted as μ(n), is an arithmetic function defined on the positive integers. It classifies integers based on their prime factorization structure. Specifically, μ(1) = 1, μ(n) = 0 if n is divisible by a squared prime (i.e., n is not square-free), and μ(n) = (-1)^k if n is the product of k distinct primes. This simple definition gives rise to a function that oscillates between -1, 0, and 1, yet its summatory behavior encodes deep information about the distribution of primes.

Why does the mobius function and inversion matter? In practical terms, many problems in computer science and mathematics naturally arise in the form F(n) = Σ_{d|n} f(d), where F is easy to compute but f is what we actually need. For example, counting primitive strings, aperiodic necklaces, or pairs of coprime integers often leads to divisor sums. Möbius inversion provides the direct formula f(n) = Σ_{d|n} μ(d) * F(n/d) to recover f without solving a system of equations. This inversion principle is the discrete analogue of the Fourier transform inversion and is fundamental to Dirichlet convolution.

Formal Definition of the Möbius Function

Formally, let n = p1^a1 * p2^a2 * ... * pk^ak be the prime factorization of n. Then:

• μ(n) = 1 if n = 1
• μ(n) = 0 if any ai > 1 (n has a squared prime factor)
• μ(n) = (-1)^k if all ai = 1 (n is square-free with k prime factors)

Thus, μ(1)=1, μ(2)=-1, μ(3)=-1, μ(4)=0, μ(5)=-1, μ(6)=1 (since 6=2*3, k=2), μ(30)=-1 (30=2*3*5, k=3), and μ(12)=0 (12=2^2*3). The function is multiplicative but not completely multiplicative, which is a crucial distinction for efficient implementation.

What is Möbius Inversion?

Möbius inversion is a theorem that comes in two forms. The divisor form states that if F(n) = Σ_{d|n} f(d) for all n, then f(n) = Σ_{d|n} μ(d) F(n/d). The summatory form states that if F(n) = Σ_{d=1 to n} f(floor(n/d)) or more commonly F(n) = Σ_{d=1 to n} f(d) * floor(n/d), similar inversion applies using the Mertens function M(n) = Σ_{i=1 to n} μ(i). The theorem also holds for functions defined on multiples: if F(n) = Σ_{n|d} f(d), then f(n) = Σ_{n|d} μ(d/n) F(d). This duality makes it applicable to both divisor sums and multiple sums, which appear frequently in algorithmic counting problems.

2. How It Works

The mechanism behind Möbius inversion rests on a single fundamental identity: Σ_{d|n} μ(d) = 1 if n=1, and 0 otherwise. This identity can be denoted as Σ_{d|n} μ(d) = [n=1], where [ ] is the Iverson bracket. This property makes μ the Dirichlet inverse of the constant function 1(n) = 1. In the language of Dirichlet convolution, (f * g)(n) = Σ_{d|n} f(d)g(n/d), we have μ * 1 = ε, where ε is the identity function (ε(1)=1, ε(n)=0 for n>1).

To see why inversion works, consider the convolution. If F = f * 1, then convolving both sides with μ gives F * μ = (f * 1) * μ = f * (1 * μ) = f * ε = f. Expanding the convolution definition yields precisely the inversion formula. This algebraic perspective reveals that Möbius inversion is not a trick but a consequence of the group structure of arithmetic functions under Dirichlet convolution. The set of arithmetic functions with f(1) ≠ 0 forms an abelian group, and μ is the unique inverse of 1.

Intuitively, μ(d) acts as an inclusion-exclusion coefficient. When we sum over divisors, we overcount. For example, to count numbers coprime to n, we might start with all numbers and subtract those divisible by each prime factor, add back those divisible by two primes, and so on. The sign (-1)^k and the zeroing out of non-square-free divisors exactly implements this principle. The summatory function M(n) = Σ_{i=1}^{n} μ(i), known as the Mertens function, measures the imbalance between even and odd numbers of prime factors among square-free integers up to n, and its growth is famously equivalent to the Riemann Hypothesis.

The Dirichlet Convolution Framework

Dirichlet convolution provides the cleanest theoretical framework. Define (f * g)(n) = Σ_{d|n} f(d)g(n/d). This operation is commutative, associative, and has identity ε. Important pairs include: id(n)=n and its convolution with μ gives Euler's totient φ = μ * id, since Σ_{d|n} φ(d) = n. Similarly, the divisor function d(n) = Σ_{d|n} 1 = (1 * 1)(n), and the sum-of-divisors function σ(n) = (id * 1)(n). Inversion allows us to go backwards: φ = μ * id, and more generally, if we can compute prefix sums of F efficiently, we can compute prefix sums of f using Dirichlet hyperbola method.

Proof Sketch of the Key Identity

To prove Σ_{d|n} μ(d) = 0 for n > 1, let n = p1^a1 ... pk^ak. Only square-free divisors contribute, so we only consider subsets of the k distinct primes. There are C(k, i) divisors with i prime factors, each contributing (-1)^i. The sum is Σ_{i=0}^{k} C(k, i) (-1)^i = (1 - 1)^k = 0 by the binomial theorem. For n=1, the sum is μ(1)=1. This simple combinatorial argument underpins the entire theory and explains why non-square-free numbers are assigned zero.

3. Implementation

Implementing the Möbius function efficiently depends on the problem constraints. For a single n up to 10^12, trial division by primes is sufficient. For all n up to N (e.g., N = 10^6 or 10^7), a modified sieve of Eratosthenes that tracks prime factor parity and squared factors is optimal with O(N log log N) or linear O(N) time. The linear sieve variant is preferred in competitive programming because it computes μ, primes, and smallest prime factors in one pass.

The core idea of the sieve is to initialize μ[i] = 1 for all i, then for each prime p, flip the sign of μ for multiples of p and zero out multiples of p^2. A naive implementation loops over primes and their multiples, which is O(N log log N). The linear sieve improves this to O(N) by ensuring each composite is sieved by its smallest prime factor exactly once.

def mobius_sieve(n):
    """
    Compute mu[1..n] using linear sieve in O(n).
    Returns list mu where mu[i] is Mobius of i.
    """
    mu = [0] * (n + 1)
    mu[1] = 1
    primes = []
    is_composite = [False] * (n + 1)
    # smallest prime factor not needed explicitly for mu
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            mu[i] = -1  # prime has one prime factor
        for p in primes:
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                # p^2 divides i * p, so not square-free
                mu[i * p] = 0
                break
            else:
                # p is new distinct prime factor
                mu[i * p] = -mu[i]
        # early break optimization
        # if p > smallest prime factor of i, handled by break above
    return mu

# Example usage
N = 20
mu = mobius_sieve(N)
for i in range(1, N + 1):
    print(f"mu({i}) = {mu[i]}")

def mobius_single(n):
    """
    Compute mu(n) for a single n via prime factorization.
    Works for n up to 1e12 efficiently if primes up to sqrt(n) are available.
    Time: O(sqrt(n))
    """
    if n == 1:
        return 1
    original_n = n
    prime_factors = 0
    p = 2
    # trial division, handle 2 separately then odd p
    cnt = 0
    while p * p <= n:
        if n % p == 0:
            n //= p
            cnt = 1
            if n % p == 0:
                # p^2 divides original number
                return 0
            prime_factors += 1
        p += 1 if p == 2 else 2  # 2,3,5,7...
        if p * p > n and n > 1:
            break
    if n > 1:
        # remaining n is prime
        prime_factors += 1
    # square-free, return (-1)^k
    return -1 if prime_factors % 2 == 1 else 1

print(mobius_single(30))  # 30=2*3*5 => -1
print(mobius_single(12))  # 12=2^2*3 => 0
print(mobius_single(6))   # 6=2*3 => 1

def mobius_inversion_example(N):
    """
    Demonstrate Mobius inversion to count square-free numbers up to N
    and to compute Euler's totient via inversion.
    F(n) = sum_{d|n} f(d)  =>  f(n) = sum_{d|n} mu(d) * F(n/d)
    Classic: phi(n) = sum_{d|n} mu(d) * (n/d)
    """
    mu = mobius_sieve(N)
    # 1. Count square-free numbers using mu: 
    # square_free_count(N) = sum_{i=1}^{sqrt(N)} mu(i) * floor(N / i^2)
    import math
    sq_free = 0
    limit = int(math.isqrt(N))
    for i in range(1, limit + 1):
        if mu[i] != 0:
            sq_free += mu[i] * (N // (i * i))
    print(f"Square-free numbers <= {N}: {sq_free}")

    # 2. Compute phi via Mobius inversion for all n <= N
    phi = [0] * (N + 1)
    for n in range(1, N + 1):
        s = 0
        # iterate divisors via mu multiples
        # phi(n) = sum_{d|n} mu(d) * n/d
        # We can compute by enumerating d dividing n
        # For demo, brute divisor enumeration
        for d in range(1, int(math.isqrt(n)) + 1):
            if n % d == 0:
                d1 = d
                d2 = n // d
                if mu[d1] != 0:
                    s += mu[d1] * (n // d1)
                if d2 != d1 and mu[d2] != 0:
                    s += mu[d2] * (n // d2)
        phi[n] = s
    return phi

phi = mobius_inversion_example(20)
print(phi[1:11])  # phi values 1..10

def dirichlet_convolution(f, g, n):
    """
    Compute (f * g)(n) = sum_{d|n} f(d) * g(n/d)
    Generic implementation for arithmetic functions f,g.
    Optimized using divisor enumeration in O(sqrt(n)).
    """
    import math
    result = 0
    sqrt_n = int(math.isqrt(n))
    for d in range(1, sqrt_n + 1):
        if n % d == 0:
            d1 = d
            d2 = n // d
            result += f[d1] * g[d2]
            if d1 != d2:
                result += f[d2] * g[d1]
    return result

def count_coprime_pairs(N):
    """
    Count pairs (a,b) with 1 <= a,b <= N and gcd(a,b)=1
    Using Mobius inversion: count = sum_{d=1}^{N} mu(d) * floor(N/d)^2
    Time O(N) with precomputed mu, O(sqrt(N)) with grouping optimization.
    """
    mu = mobius_sieve(N)
    total = 0
    for d in range(1, N + 1):
        if mu[d] != 0:
            t = N // d
            total += mu[d] * t * t
    return total

# Grouping optimization for large N (Dirichlet hyperbola / floor division trick)
def count_coprime_pairs_fast(N):
    mu = mobius_sieve(N)
    # prefix sums of mu: Mertens function
    mertens = [0] * (N + 1)
    for i in range(1, N + 1):
        mertens[i] = mertens[i - 1] + mu[i]
    
    total = 0
    l = 1
    while l <= N:
        q = N // l
        r = N // q  # max r with same floor value
        # sum mu[l..r] * q^2
        mu_sum = mertens[r] - mertens[l - 1]
        total += mu_sum * q * q
        l = r + 1
    return total

print(count_coprime_pairs(10))
print(count_coprime_pairs_fast(10))

4. Step-by-Step Example

Let us walk through a concrete example to solidify the theory. Suppose we define F(n) = Σ_{d|n} f(d) and we know F(n) = n^2 for all n. Our goal is to recover f(12) using Möbius inversion. This is a typical scenario where F is easy to observe (e.g., sum of f over divisors) but f is the hidden quantity we need.

First, compute μ(d) for all divisors d of 12. Divisors of 12 are 1, 2, 3, 4, 6, 12. Their Möbius values are: μ(1)=1, μ(2)=-1 (prime), μ(3)=-1, μ(4)=0 (2^2 divides 4), μ(6)=1 (2*3, two primes), μ(12)=0 (2^2 divides 12). The inversion formula says f(12) = Σ_{d|12} μ(d) * F(12/d). So we need F(12/d) for each d.

Compute each term: For d=1: μ(1)*F(12)=1*144=144. For d=2: μ(2)*F(6)= -1*36= -36. For d=3: μ(3)*F(4)= -1*16= -16. For d=4: μ(4)*F(3)=0*9=0. For d=6: μ(6)*F(2)=1*4=4. For d=12: μ(12)*F(1)=0*1=0. Summing: 144 -36 -16 +0 +4 +0 = 96. Therefore f(12)=96. We can verify by brute force: we need a function f such that Σ_{d|12} f(d)=144. If we compute f for all divisors recursively, we would get the same result, but inversion gives it directly.

Counting Coprime Pairs Example

A more algorithmic example is counting coprime pairs. Let N=6. We want to count pairs (a,b) with 1 ≤ a,b ≤ N and gcd(a,b)=1. Brute force enumeration gives 23 such pairs out of 36. Using Möbius inversion, we use the identity [gcd(a,b)=1] = Σ_{d|gcd(a,b)} μ(d). Summing over all pairs: count = Σ_{a=1}^{N} Σ_{b=1}^{N} Σ_{d|a, d|b} μ(d) = Σ_{d=1}^{N} μ(d) * floor(N/d)^2. Compute: floor(6/1)=6, floor(6/2)=3, floor(6/3)=2, floor(6/4)=1, floor(6/5)=1, floor(6/6)=1. With μ: 1*36 + (-1)*9 + (-1)*4 + 0*1 + (-1)*1 + 1*1 = 36-9-4-1+1=23, which matches brute force. This technique generalizes to counting k-tuples with gcd 1 and is O(N) after sieve.

Verifying with Dirichlet Convolution

Let us verify the Euler totient inversion. We know Σ_{d|n} φ(d) = n. Take n=6. Divisors: 1,2,3,6. φ(1)=1, φ(2)=1, φ(3)=2, φ(6)=2. Sum=6. Now invert: φ(6) should equal Σ_{d|6} μ(d) * (6/d). Compute: μ(1)*6=6, μ(2)*3=-3, μ(3)*2=-2, μ(6)*1=1. Sum=6-3-2+1=2, which matches φ(6). This demonstrates how μ inverts the constant 1 function to recover φ from id. The same pattern holds for any Dirichlet pair, making the method highly reusable.

5. Complexity Analysis

Complexity analysis for Möbius-related algorithms depends heavily on whether we need μ for a single value or for all values up to N, and whether we need to perform inversion summations. The sieve preprocessing dominates when N is large, but once μ is precomputed, each inversion query becomes a divisor enumeration problem.

For single μ(n) via trial division, the worst-case time is O(√n) divisions, which is feasible for n up to 10^12 but becomes slow for many queries. Using a precomputed prime list up to √n reduces the constant factor but not the asymptotic complexity. For Pollard-Rho factorization, μ(n) can be computed in sub-exponential time for n up to 10^18, but this is overkill for most competitive programming constraints.

For the sieve approach, the classic Eratosthenes-based Möbius sieve runs in O(N log log N) time and O(N) space, which is effectively linear for N up to 10^7. The linear sieve achieves O(N) time with a slightly higher constant but better cache behavior. The inversion step itself, if done naively for all n ≤ N via divisor loops, costs O(N log N) using harmonic series summation: Σ_{d=1}^{N} N/d = N log N. Using Dirichlet hyperbola optimization, summatory queries like Σ_{i=1}^{N} floor(N/i) can be done in O(√N) by grouping equal quotients.

The space complexity is typically dominated by the μ array and prefix sums, both O(N). For N = 10^7, storing μ as an array of signed bytes or integers requires ~40 MB in Python (much more due to Python object overhead), so in practice PyPy with array('b') or numpy is used, or the algorithm is implemented in a lower-level language. In Python, for N up to 10^6, the linear sieve is comfortably fast; beyond that, PyPy and optimized loops with Numba are recommended.

6. Variations and Optimizations

Several variations and optimizations make Möbius inversion practical for large constraints. The most important is the floor division grouping trick, also known as the Dirichlet hyperbola method. Since floor(N / i) takes only O(√N) distinct values, we can group intervals [l, r] where the quotient is constant and use prefix sums of μ to process each interval in O(1). This reduces summatory inversion from O(N) to O(√N).

Another optimization is the Mertens function caching with memoization and divide-and-conquer. For very large N up to 10^11, we cannot sieve up to N, but we can compute M(N) = Σ_{i=1}^{N} μ(i) recursively using M(N) = 1 - Σ_{i=2}^{N} M(N // i) with grouping and memoization. This technique, combined with a sieve up to N^{2/3}, yields an O(N^{2/3}) algorithm for summatory Möbius queries, which is essential for problems like counting square-free numbers up to 10^12.

The linear sieve can be extended to compute multiple arithmetic functions simultaneously. In one pass, we can compute μ, φ, smallest prime factor (SPF), and the divisor count. This amortizes the sieve cost when multiple inversions are needed. Additionally, using a bitset or bytearray for is_composite reduces memory and improves cache locality.

Segmented Sieve for Large N

When N is large but the interval [L, R] is small (e.g., R - L ≤ 10^6, R up to 10^12), a segmented sieve for μ is used. We generate primes up to √R, then for each prime p, mark multiples of p and p^2 in the segment. This allows computing μ for numbers in [L, R] without sieving up to R, using O(√R + (R-L) log log R) time and O(R-L) space.

Multiplicative Property and Caching

Since μ is multiplicative, μ(a*b) = μ(a)*μ(b) when gcd(a,b)=1, and 0 otherwise. This property enables caching factorizations and using a dictionary for memoization of μ for numbers with repeated queries. For dynamic programming over divisors, storing μ in a hash map for only square-free numbers can save space when N is sparse.

7. Real-World Applications

While the Möbius function originates in pure number theory, its applications extend to computer science, cryptography, and engineering systems where periodicities, coprimality, and inclusion-exclusion are relevant. The inversion principle is a general tool for counting primitive objects versus all objects.

In cryptography, the Möbius function appears in the analysis of RSA and cyclic groups. The number of primitive roots modulo a prime p, the count of aperiodic necklaces used in de Bruijn sequences, and the enumeration of irreducible polynomials over finite fields all involve Möbius inversion. For example, the number of monic irreducible polynomials of degree n over GF(q) is (1/n) Σ_{d|n} μ(d) q^{n/d}, a direct application of inversion that is critical for constructing finite fields for AES and error-correcting codes.

In string algorithms and combinatorics on words, Möbius inversion counts primitive strings. A string is primitive if it is not a repetition of a smaller string. The number of primitive strings of length n over an alphabet of size k is Σ_{d|n} μ(d) k^{n/d}. This is used in pattern matching, bioinformatics (counting distinct DNA motifs), and data compression. Similarly, the number of aperiodic necklaces (Lyndon words) is (1/n) Σ_{d|n} μ(d) k^{n/d}, used in generating de Bruijn sequences for robot navigation and genome assembly.

In distributed systems and hashing, counting coprime pairs is relevant to hash collision analysis and load balancing. If two hash functions use moduli that are not coprime, collisions correlate. Möbius inversion provides O(N) or O(√N) methods to estimate the fraction of coprime pairs in a range, which informs the choice of table sizes in hash tables and sharding strategies in databases.

In web servers and databases, the principle appears indirectly in query optimization for counting distinct values with gcd constraints and in the analysis of periodic tasks. For instance, counting the number of integers up to N that are coprime to a set of moduli (used in wheel sieves for prime generation) is an inclusion-exclusion that is exactly Möbius inversion. Modern prime sieves for generating primes up to 10^9 for cryptographic key generation rely on segmented Möbius sieves.

8. Comparison with Alternatives

Möbius inversion is not the only way to handle divisor sums; several alternative techniques exist, each with trade-offs in complexity, generality, and implementation difficulty. Understanding when to use Möbius versus brute force, direct inclusion-exclusion, or generating functions is key to choosing the right tool.

Brute force enumeration of divisors or pairs is simple to implement but scales poorly. For counting coprime pairs up to N, brute force checks gcd for each of N^2 pairs, costing O(N^2 log N), which is infeasible for N > 10^4. Inclusion-exclusion over prime factors is more efficient but requires factoring N and enumerating subsets of its distinct prime factors (2^k subsets), which is exponential in k. Möbius inversion generalizes inclusion-exclusion to all integers up to N with O(N) sieve cost, making it superior when N is large but the number of queries is many.

Euler's totient summatory technique is a specialized alternative for problems involving gcd sums. The identity Σ_{d|n} φ(d) = n can sometimes replace Möbius inversion when the function involves n/d. However, φ is specific to that identity, while Möbius inversion is generic for any F = f * 1. Dirichlet convolution via FFT or NTT is an alternative for very large N where convolution is performed in the frequency domain, but it is complex and only beneficial for polynomial multiplication analogies.

In practice, Möbius inversion is the preferred method for competitive programming and algorithmic number theory when the problem can be expressed as a divisor sum. Its O(N) preprocessing is amortized over many queries, and the O(√N) grouped summation makes it feasible for N up to 10^12 with memoization. For single-query problems with small N, brute force may be simpler and less error-prone, but for any problem requiring counting square-free numbers, primitive strings, or coprime tuples at scale, Möbius inversion is the standard solution.

9. Common Mistakes and Best Practices

Implementing Möbius function and inversion correctly requires attention to several subtle pitfalls that can lead to off-by-one errors, incorrect zero handling, or performance degradation. The most common mistake is mishandling μ(1) and non-square-free numbers. Forgetting that μ(1)=1 (not 0) breaks the inversion identity, and failing to zero out multiples of p^2 leads to incorrect signs. Always initialize μ[1]=1 and explicitly set μ[p^2 * k]=0.

Another frequent error is integer overflow and floating-point inaccuracies when computing floor(N / i) or i*i for large N. In Python, integers are arbitrary precision, but in languages like C++ or Java, i*i may overflow 32-bit integers when N approaches 10^12. Use 64-bit integers and integer square root functions. When using the grouping optimization, the calculation of r = N // (N // l) must be done with integer division to avoid off-by-one in interval boundaries.

Performance pitfalls include using a naive O(N log N) divisor loop for each n when a harmonic series loop is more efficient. For computing f for all n ≤ N via inversion, the optimal approach is to iterate over d and add μ(d) * F(n/d) to all multiples of d, which is O(N log N), rather than factoring each n individually. In Python, pure loops over N=10^6 may be slow; using PyPy, Numba's @jit, or numpy vectorization is recommended. Also, avoid recomputing μ for each query; precompute once and reuse.

Best Practices Checklist

• Precompute μ up to N with linear sieve and store prefix sums M(n) for O(1) range queries.
• Use bytearray or array('b') for μ to reduce memory in Python; use list of ints only for moderate N.
• Validate with small cases: check Σ_{d|n} μ(d) equals 1 if n=1 else 0 for n up to 100.
• For summatory problems, always implement the O(√N) grouping trick; test interval boundaries thoroughly.
• Handle edge cases: n=1, n prime, n = p^2, and large N where N // i = 0.
• Document the Dirichlet pair: clearly state F = f * 1 and f = F * μ to avoid confusion about division direction.

Testing strategy should include comparing sieve results against brute force μ for n up to 1000, verifying inversion on known pairs like (φ, id) and (μ, 1), and stress-testing coprime counting against brute force for N up to 100. For segmented sieves, test with intervals crossing prime squares to ensure zeroing logic is correct.

10. Interview Questions

Möbius function and inversion appear in advanced algorithm interviews, especially for roles involving cryptography, competitive programming, or mathematical software. Interviewers test both theoretical understanding and the ability to implement efficiently under constraints.

Q1: How would you compute μ(n) for all n up to 10^6 efficiently? What is the time and space complexity?

Answer: Use a linear sieve. Initialize μ[1]=1, maintain primes list and is_composite array. For each i from 2 to N, if not composite, it is prime, append to primes and set μ[i] = -1. For each prime p in primes, if i * p > N break; mark i*p composite; if i % p == 0 then μ[i*p]=0 break, else μ[i*p] = -μ[i]. This runs in O(N) time and O(N) space. The key insight is each composite is generated by its smallest prime factor exactly once, and the multiplicative property handles sign flipping. Follow-up: explain why we break when i % p == 0 (to avoid marking with larger primes and to correctly zero out squares).

Q2: Given F(n) = Σ_{d|n} f(d), derive f(n) in terms of F and μ. Prove the inversion formula.

Answer: f(n) = Σ_{d|n} μ(d) F(n/d). Proof uses Dirichlet convolution: define (f * g)(n)=Σ_{d|n} f(d)g(n/d). Let 1(n)=1, ε(n)=[n=1]. Given F = f * 1. Convolve both sides with μ: F * μ = f * 1 * μ = f * ε = f, since 1 * μ = ε (proven via Σ_{d|n} μ(d)=[n=1]). Expanding gives f(n)= Σ_{d|n} μ(d) F(n/d). Be prepared to prove Σ_{d|n} μ(d)=0 for n>1 using binomial theorem on square-free divisors. This tests understanding of convolution algebra versus rote memorization.

Q3: Count the number of pairs (a,b) with 1 ≤ a,b ≤ N and gcd(a,b)=1. How does Möbius inversion help and what is the optimized complexity?

Answer: Use identity [gcd(a,b)=1]= Σ_{d|gcd(a,b)} μ(d). Summing over all pairs gives count = Σ_{d=1}^{N} μ(d) floor(N/d)^2. Naive O(N) after O(N) sieve. Optimize to O(√N) with grouping: floor(N/d) takes O(√N) distinct values, so group intervals [l,r] where quotient q = N//l constant, use prefix sums of μ (Mertens) to compute sum_{d=l}^{r} μ(d) * q^2 in O(1) per group. Precompute μ up to N with sieve, build prefix sums, then iterate l=1 while l ≤ N: q=N//l, r=N//q, ans += (M[r]-M[l-1])*q*q, l=r+1. This is crucial for N up to 10^7 or larger with memoization for N up to 10^11.

Q4: What is the difference between the Möbius function being multiplicative versus completely multiplicative? Give a counterexample.

Answer: Multiplicative means f(ab)=f(a)f(b) when gcd(a,b)=1. Completely multiplicative requires it for all a,b. μ is multiplicative but not completely multiplicative. Counterexample: μ(2)=-1, μ(4)=0, but μ(2)*μ(2)=1 ≠ 0 = μ(4). The failure occurs because 2 and 2 are not coprime and 4 has a squared factor. This distinction matters for sieve implementation: we cannot compute μ[i*p] as μ[i]*μ[p] when p divides i; instead we must set to 0. Interviewers use this to check attention to the square-free condition.

Q5: How would you count square-free numbers up to N using Möbius inversion?

Answer: An integer is square-free iff it is not divisible by any p^2. Using inclusion-exclusion, count = Σ_{i=1}^{√N} μ(i) floor(N / i^2). Explanation: floor(N / i^2) counts numbers divisible by i^2, and μ(i) provides inclusion-exclusion signs, zeroing non-square-free i. Compute μ up to √N via sieve, then sum. Complexity O(√N) after sieve. For N=10^12, √N=10^6, feasible. Follow-up: extend to counting k-free numbers (not divisible by p^k) by replacing i^2 with i^k and using the same formula with μ.