Skip to content

Coprime Counting and the Mobius Connection

Pillar: Set — "Count integers coprime to \(n\) by IE on prime factors: subtract multiples of each prime, add back intersections. This derivation IS the Euler product formula."

The Setup

You saw in Ch4 L5 that \(\phi(12) = 4\) — there are four integers in \([1, 12]\) coprime to \(12\). The product formula \(\phi(n) = n \prod(1 - 1/p_i)\) was stated and derived via inclusion-exclusion in a few lines.

Now flip the question. Instead of counting coprimes to \(n\) inside \([1, n]\), count them in an arbitrary range: how many integers in \([1, N]\) are coprime to some fixed \(m\)?

Take \(N = 20\), \(m = 6\). The prime factors of \(6\) are \(2\) and \(3\). You need to count integers in \([1, 20]\) that are NOT divisible by \(2\) or \(3\). Listing them out: \(\{1, 5, 7, 11, 13, 17, 19\}\) — that's \(7\).

This generalization shows up everywhere. Counting coprime pairs in an array, computing totient sums, problems that ask "how many integers in \([L, R]\) satisfy \(\gcd(k, m) = 1\)." The core tool is inclusion-exclusion on the prime factor set of \(m\), and the correction weights that appear have a name: the Mobius function.

IE on Prime Factors

Let \(p_1, p_2, \ldots, p_k\) be the distinct prime factors of \(m\). Define \(A_i\) as the set of integers in \([1, N]\) divisible by \(p_i\). You want the count of integers NOT in any \(A_i\):

\[|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_k}| = N - |A_1 \cup A_2 \cup \cdots \cup A_k|\]

By inclusion-exclusion on the union:

\[|A_1 \cup \cdots \cup A_k| = \sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \cdots + (-1)^{k+1}|A_1 \cap \cdots \cap A_k|\]

Each intersection \(|A_{i_1} \cap \cdots \cap A_{i_r}|\) counts multiples of \(p_{i_1} p_{i_2} \cdots p_{i_r}\) in \([1, N]\). Since the \(p_i\) are distinct primes, their product is their LCM. The count of multiples of \(d\) in \([1, N]\) is \(\lfloor N/d \rfloor\).

So the coprime count is:

\[\text{coprime}(N, m) = \sum_{S \subseteq \{p_1, \ldots, p_k\}} (-1)^{|S|} \left\lfloor \frac{N}{\prod_{p \in S} p} \right\rfloor\]

The empty subset contributes \(\lfloor N/1 \rfloor = N\).

Worked Example

\(N = 20\), \(m = 30 = 2 \times 3 \times 5\). Three distinct primes.

Enumerate all \(2^3 = 8\) subsets:

| Subset \(S\) | \(\prod S\) | \((-1)^{|S|}\) | \(\lfloor 20 / \prod S \rfloor\) | Contribution | |------------|-----------|---------------|-------------------------------|--------------| | \(\emptyset\) | \(1\) | \(+1\) | \(20\) | \(+20\) | | \(\{2\}\) | \(2\) | \(-1\) | \(10\) | \(-10\) | | \(\{3\}\) | \(3\) | \(-1\) | \(6\) | \(-6\) | | \(\{5\}\) | \(5\) | \(-1\) | \(4\) | \(-4\) | | \(\{2,3\}\) | \(6\) | \(+1\) | \(3\) | \(+3\) | | \(\{2,5\}\) | \(10\) | \(+1\) | \(2\) | \(+2\) | | \(\{3,5\}\) | \(15\) | \(+1\) | \(1\) | \(+1\) | | \(\{2,3,5\}\) | \(30\) | \(-1\) | \(0\) | \(0\) |

Sum: \(20 - 10 - 6 - 4 + 3 + 2 + 1 + 0 = 6\).

Verify: the integers in \([1, 20]\) coprime to \(30\) are \(\{1, 7, 11, 13, 17, 19\}\). Six of them. Correct.

This IS the Euler Product Formula

When \(N = m\), the coprime count is \(\phi(m)\) by definition. The floor terms simplify because \(m\) is divisible by every product of its own prime factors:

\[\phi(m) = \sum_{S \subseteq \{p_1, \ldots, p_k\}} (-1)^{|S|} \frac{m}{\prod_{p \in S} p}\]

Factor out \(m\):

\[\phi(m) = m \sum_{S \subseteq \{p_1, \ldots, p_k\}} (-1)^{|S|} \frac{1}{\prod_{p \in S} p} = m \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)\]

The last step is the key observation: the sum over all subsets of \(\{p_1, \ldots, p_k\}\) of \((-1)^{|S|} / \prod S\) factors into a product — each prime contributes a factor of \((1 - 1/p_i)\) independently. This is exactly the expansion of the product \(\prod(1 - 1/p_i)\).

So the inclusion-exclusion derivation you just traced IS the proof of the Euler product formula from Ch4 L5. The two arguments are the same argument. Ch4 L5 stated it and showed the mechanics. Now you've seen the underlying IE structure that makes it work.

The Mobius Function

The IE correction weights — \(+1\) for even-sized subsets, \(-1\) for odd-sized, applied to squarefree products of primes — have a name. They're values of the Mobius function \(\mu\).

Definition. For a positive integer \(n\):

\[\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n \text{ is squarefree with } k \text{ distinct prime factors} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}\]

A number is squarefree if no prime appears more than once in its factorization. So \(30 = 2 \times 3 \times 5\) is squarefree, but \(12 = 2^2 \times 3\) is not.

Table of \(\mu(n)\) for \(n = 1\) to \(12\)

\(n\) Factorization Squarefree? \(\mu(n)\)
\(1\) \(1\) Yes \(1\)
\(2\) \(2\) Yes \(-1\)
\(3\) \(3\) Yes \(-1\)
\(4\) \(2^2\) No \(0\)
\(5\) \(5\) Yes \(-1\)
\(6\) \(2 \times 3\) Yes \(1\)
\(7\) \(7\) Yes \(-1\)
\(8\) \(2^3\) No \(0\)
\(9\) \(3^2\) No \(0\)
\(10\) \(2 \times 5\) Yes \(1\)
\(11\) \(11\) Yes \(-1\)
\(12\) \(2^2 \times 3\) No \(0\)

The pattern: primes get \(-1\), products of two distinct primes get \(+1\), products of three distinct primes get \(-1\), and anything with a squared prime factor gets \(0\).

The Key Property

The most important fact about \(\mu\) is this:

\[\sum_{d \mid n} \mu(d) = [n = 1]\]

where \([n = 1]\) is \(1\) when \(n = 1\) and \(0\) otherwise. This is the Iverson bracket notation.

Proof. For \(n = 1\), the only divisor is \(1\), and \(\mu(1) = 1\). Done.

For \(n > 1\), factor \(n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\). Only squarefree divisors of \(n\) contribute to the sum (non-squarefree divisors have \(\mu = 0\)). A squarefree divisor of \(n\) is a product of some subset of \(\{p_1, \ldots, p_k\}\).

So the sum becomes:

\[\sum_{d \mid n} \mu(d) = \sum_{S \subseteq \{p_1, \ldots, p_k\}} (-1)^{|S|} = \sum_{j=0}^{k} \binom{k}{j}(-1)^j = (1 - 1)^k = 0\]

The last step is the binomial theorem with \(x = -1\): \((1 + (-1))^k = 0\) for \(k \geq 1\). This is the alternating sum identity from Ch5 L1.

Trace it for \(n = 12\). The divisors are \(1, 2, 3, 4, 6, 12\). Their \(\mu\) values: \(1, -1, -1, 0, 1, 0\). Sum: \(1 - 1 - 1 + 0 + 1 + 0 = 0\). The squarefree divisors (\(1, 2, 3, 6\)) correspond to the subsets of \(\{2, 3\}\), and their \(\mu\) values are exactly the IE signs.

\(\mu\) as the IE Correction Weight

Rewrite the coprime counting formula using \(\mu\). The squarefree divisors of \(m\) that appear in the IE sum are exactly the divisors \(d\) where \(\mu(d) \neq 0\), and the sign for each is \(\mu(d)\). So:

\[\text{coprime}(N, m) = \sum_{\substack{d \mid m \\ d \text{ squarefree}}} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor = \sum_{d \mid m} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor\]

The second equality holds because the non-squarefree divisors contribute \(\mu(d) = 0\) and vanish from the sum.

This is cleaner than enumerating subsets of prime factors. It also hints at something deeper: \(\mu\) is the function that "inverts" summation over divisors. If you define \(g(n) = \sum_{d \mid n} f(d)\), then you can recover \(f\) from \(g\) using \(\mu\):

\[f(n) = \sum_{d \mid n} \mu(d) \, g(n/d)\]

This is Mobius inversion, and it's one of the most powerful tools in analytic number theory and competitive programming. The full treatment comes in Ch9 L3 — this lesson just shows you where \(\mu\) comes from and why it appears.

Computing \(\mu\) via Sieve

You can compute \(\mu(n)\) for all \(n\) up to some limit using the linear sieve from Ch2 L4. The linear sieve gives you the smallest prime factor of every number, plus it processes each composite exactly once. During this process, track two things: whether the number is squarefree, and the parity of its prime factor count.

The rules during the linear sieve:

  • If current is prime: \(\mu(\text{current}) = -1\) (one prime factor, squarefree).
  • For composite \(= \text{current} \times p\) where \(p \nmid \text{current}\): the prime \(p\) is a new distinct factor, so \(\mu(\text{composite}) = -\mu(\text{current})\) (sign flips).
  • For composite \(= \text{current} \times p\) where \(p \mid \text{current}\): the prime \(p\) appears at least twice, so \(\mu(\text{composite}) = 0\) (not squarefree).

The Code

Sieve Mu

vector<int> sieveMu(int limit) {
    vector<int> mu(limit + 1, 0);
    vector<int> smallestPrimeFactor(limit + 1, 0);
    vector<int> primes;
    mu[1] = 1;
    for (int current = 2; current <= limit; current++) {
        if (smallestPrimeFactor[current] == 0) {
            smallestPrimeFactor[current] = current;
            primes.push_back(current);
            mu[current] = -1;
        }
        for (int primeIndex = 0; primeIndex < (int)primes.size(); primeIndex++) {
            long long composite = (long long)current * primes[primeIndex];
            if (composite > limit) break;
            smallestPrimeFactor[composite] = primes[primeIndex];
            if (current % primes[primeIndex] == 0) {
                mu[composite] = 0;
                break;
            }
            mu[composite] = -mu[current];
        }
    }
    return mu;
}

\(O(n)\) time, \(O(n)\) space — same as the linear sieve itself.

Count Coprime in Range via IE

Factor \(m\) into distinct primes, then iterate over all \(2^k\) subsets using a bitmask. This is the direct IE approach.

long long countCoprimeInRange(long long rangeEnd, long long modulus) {
    vector<long long> distinctPrimes;
    long long temp = modulus;
    for (long long factor = 2; factor * factor <= temp; factor++) {
        if (temp % factor == 0) {
            distinctPrimes.push_back(factor);
            while (temp % factor == 0) temp /= factor;
        }
    }
    if (temp > 1) distinctPrimes.push_back(temp);
    int primeCount = distinctPrimes.size();
    long long coprimeCount = 0;
    for (int mask = 0; mask < (1 << primeCount); mask++) {
        long long product = 1;
        int bitsSet = __builtin_popcount(mask);
        for (int bit = 0; bit < primeCount; bit++) {
            if (mask >> bit & 1) product *= distinctPrimes[bit];
        }
        if (bitsSet % 2 == 0) coprimeCount += rangeEnd / product;
        else coprimeCount -= rangeEnd / product;
    }
    return coprimeCount;
}

\(O(\sqrt{m} + 2^k)\) time where \(k\) is the number of distinct prime factors of \(m\). Since \(k \leq 15\) for any \(m < 2^{63}\) (the product of the first \(15\) primes exceeds \(10^{17}\)), the bitmask loop is negligible.

Common Mistakes

  • Forgetting that \(\mu(n) = 0\) for non-squarefree \(n\). If you compute \(\mu\) by just counting prime factors and applying \((-1)^k\) without checking squarefreeness, you'll get wrong answers for \(4, 8, 9, 12\), etc. The squared-prime check is essential.

  • Overflow in the bitmask product. When \(m\) has many prime factors, the product of a large subset can overflow long long. For the coprime counting function, \(m\) itself fits in long long, so any product of a subset of its prime factors also fits. But if you're combining this with other multiplications, be careful.

  • Confusing \(\mu\) with the IE sign. The IE sign for a subset of size \(j\) is \((-1)^j\). The Mobius function \(\mu(d)\) equals \((-1)^j\) only when \(d\) is squarefree with \(j\) prime factors. For non-squarefree \(d\), \(\mu(d) = 0\) — it's not \((-1)^j\). This distinction matters when summing over ALL divisors of \(m\), not just squarefree ones.

Quick Recap

  • Count integers in \([1, N]\) coprime to \(m\) by IE on the distinct prime factors of \(m\): subtract multiples of each \(p_i\), add back multiples of \(p_i p_j\), and so on. The formula iterates over all \(2^k\) subsets via bitmask.
  • When \(N = m\), this coprime count IS \(\phi(m)\), and the IE formula collapses to the Euler product formula \(\phi(m) = m \prod(1 - 1/p_i)\).
  • The Mobius function \(\mu(n)\) assigns the IE correction weight to each divisor: \((-1)^k\) for squarefree numbers with \(k\) prime factors, \(0\) for non-squarefree.
  • Key property: \(\sum_{d \mid n} \mu(d) = [n = 1]\). Proof uses the alternating sum identity \((1 - 1)^k = 0\).
  • Compute \(\mu\) for all values up to a limit in \(O(n)\) time using the linear sieve. Full Mobius inversion in Ch9 L3.

Problems

Problem Link Difficulty Focus
CSES — Counting Coprime Pairs cses.fi/problemset/task/2417 Medium IE over prime factors; count pairs with \(\gcd = 1\)
LC 2183 — Count Array Pairs Divisible by K leetcode.com/problems/count-array-pairs-divisible-by-k Hard GCD-based pair counting; divisor enumeration with \(\mu\)