Definition

Multiplicative Function: A number-theoretic function f where f(1) = 1 and f(ab) = f(a)f(b) for all coprime positive integers a, b.

Completely Multiplicative Function: A number-theoretic functon f where f(1) = 1 and f(ab) = f(a)f(b) for all positive integers a, b.

Common Functions

Common Multiplicative Functions:

1. Euler's Totient Function φ: φ(n) counts positive integers ≤ n that are coprime to n
2. GCD with constant k: gcd(k, n) where k is fixed
3. Divisor Function σₖ: σₖ(n) = sum of k-th powers of n's positive divisors
   • Divisor count σ₀: σ₀(n) = number of positive divisors of n
   • Divisor sum σ₁: σ₁(n) = sum of positive divisors of n
4. Möbius Function μ

Common Completely Multiplicative Functions:

1. Modular Inverse (when exists)
2. Identity Function ε: ε(n) = [n = 1]
3. Power Function Idₖ: Idₖ(n) = nᵏ
   • Constant function 1: 1(n) = 1 = Id₀(n)
   • Identity function Id: Id(n) = n = Id₁(n)

Sieve Methods for Multiplicative Functions

Euler's sieve can compute multiplicative function values in O(n) time. Each n is eliminated as i × pⱼ, where i is n's largest proper divisor and pⱼ is n's smallest prime factor.

Euler's Totient Function

1. n is prime: φ(n) = n - 1
2. i | pⱼ (i contains all prime factors of n): φ(n) = n × ∏(pᵢ-1)/pᵢ = pⱼ × φ(i)
3. i ∤ pⱼ: φ(n) = φ(i) × φ(pⱼ)

void computeTotient(int limit) {
    phi[1] = 1;
    is_composite[1] = true;
    for (int current = 2; current <= limit; current++) {
        if (!is_composite[current]) {
            primes.emplace_back(current);
            phi[current] = current - 1;
        }
        for (int idx = 0; idx < primes.size() && current * primes[idx] <= limit; idx++) {
            int product = current * primes[idx];
            is_composite[product] = true;
            if (current % primes[idx] == 0) {
                phi[product] = phi[current] * primes[idx];
                break;
            } else {
                phi[product] = phi[current] * phi[primes[idx]];
            }
        }
    }
}

Möbius Function

1. n is prime: μ(n) = -1
2. i | pⱼ: μ(i × pⱼ) = 0
3. i ∤ pⱼ: μ(i × pⱼ) = -μ(i)

void computeMobius(int limit) {
    mobius[1] = 1;
    is_composite[1] = true;
    for (int num = 2; num <= limit; num++) {
        if (!is_composite[num]) {
            primes.emplace_back(num);
            mobius[num] = -1;
        }
        for (int idx = 0; idx < primes.size() && num * primes[idx] <= limit; idx++) {
            int product = num * primes[idx];
            is_composite[product] = true;
            if (num % primes[idx] == 0) {
                mobius[product] = 0;
                break;
            } else {
                mobius[product] = -mobius[num];
            }
        }
    }
}

Modular Inverses

invₙ = (mod - ⌊mod/n⌋) × inv_(mod mod n) mod mod

inv[1] = 1;
for (int i = 2; i < MOD; i++) {
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

GCD with Fixed Constant k

1. n is prime:
   • n = k: gcd(k, n) = n
   • n ≠ k: gcd(k, n) = 1
2. i | pⱼ:
   • pⱼ | (n/gᵢ): gcd(k, n) = gcd(k, i) × pⱼ
   • pⱼ ∤ (n/gᵢ): gcd(k, n) = gcd(k, i)
3. i ∤ pⱼ: gcd(k, n) = gcd(i, n) × gcd(pⱼ, n)

void computeGcdWithConstant(int limit, int constant) {
    gcd_val[1] = 1;
    is_composite[1] = true;
    for (int i = 2; i <= limit; i++) {
        if (!is_composite[i]) {
            primes.emplace_back(i);
            gcd_val[i] = (constant % i == 0) ? i : 1;
        }
        for (int idx = 0; idx < primes.size() && i * primes[idx] <= limit; idx++) {
            int product = i * primes[idx];
            is_composite[product] = true;
            if (i % primes[idx] == 0) {
                if (constant / gcd_val[i] % primes[idx] == 0) {
                    gcd_val[product] = gcd_val[i] * primes[idx];
                } else {
                    gcd_val[product] = gcd_val[i];
                }
                break;
            } else {
                gcd_val[product] = gcd_val[i] * gcd_val[primes[idx]];
            }
        }
    }
}

Divisor Count Function

Let n = ∏pᵢ^qᵢ where pᵢ are distinct primes ordered increasingly.

Let expₙ be q₁ from the factorization.

1. n is prime: σ₀(n) = 2, expₙ = 1
2. i | pⱼ: σ₀(n) = σ₀(i)/(expᵢ+1) × (expᵢ+2), expₙ = expᵢ + 1
3. i ∤ pⱼ: σ₀(n) = σ₀(i) × σ₀(pⱼ), expₙ = 1

void computeDivisorCount(int limit) {
    divisor_count[1] = 1;
    is_composite[1] = true;
    for (int i = 2; i <= limit; i++) {
        if (!is_composite[i]) {
            divisor_count[i] = 2;
            exponent[i] = 1;
            primes.emplace_back(i);
        }
        for (int idx = 0; idx < primes.size() && i * primes[idx] <= limit; idx++) {
            int product = i * primes[idx];
            is_composite[product] = true;
            if (i % primes[idx] == 0) {
                divisor_count[product] = divisor_count[i] / (exponent[i] + 1) * (exponent[i] + 2);
                exponent[product] = exponent[i] + 1;
                break;
            } else {
                divisor_count[product] = divisor_count[i] * divisor_count[primes[idx]];
                exponent[product] = 1;
            }
        }
    }
}

Divisor Sum Function

Let σ(n) = ΣΣpᵢʲ for all prime factors and their powers.

Let sum_powₙ = Σp₁ʲ for j from 0 to q₁.

1. n is prime: σ(n) = sum_powₙ = n + 1
2. i | pⱼ: σ(n) = σ(i)/sum_powᵢ × (sum_powᵢ × pⱼ + 1), sum_powₙ = sum_powᵢ × pⱼ + 1
3. i ∤ pⱼ: σ(n) = σ(i) × σ(pⱼ), sum_powₙ = pⱼ + 1

void computeDivisorSum(int limit) {
    divisor_sum[1] = 1;
    for (int i = 2; i <= limit; i++) {
        if (!is_composite[i]) {
            primes.emplace_back(i);
            divisor_sum[i] = power_sum[i] = i + 1;
        }
        for (int idx = 0; idx < primes.size() && i * primes[idx] <= limit; idx++) {
            int product = i * primes[idx];
            is_composite[product] = true;
            if (i % primes[idx] == 0) {
                divisor_sum[product] = divisor_sum[i] / power_sum[i] * (power_sum[i] * primes[idx] + 1);
                power_sum[product] = power_sum[i] * primes[idx] + 1;
                break;
            } else {
                divisor_sum[product] = divisor_sum[i] * divisor_sum[primes[idx]];
                power_sum[product] = primes[idx] + 1;
            }
        }
    }
}

Sum of Squared Divisors

void computeSquaredDivisorSum(int limit) {
    divisor_count[1] = squared_sum[1] = power_sum[1] = 1;
    for (int i = 2; i <= limit; i++) {
        if (!is_composite[i]) {
            power_sum[i] = 1;
            geometric[i] = 1LL * i * i + 1;
            divisor_count[i] = 2;
            squared_sum[i] = geometric[i];
            primes.emplace_back(i);
        }
        for (int idx = 0, product; idx < primes.size() && i * primes[idx] <= limit; idx++) {
            product = i * primes[idx];
            is_composite[product] = true;
            if (i % primes[idx] == 0) {
                power_sum[product] = power_sum[i] + 1;
                geometric[product] = geometric[i] * primes[idx] * primes[idx] + 1;
                divisor_count[product] = divisor_count[i] / power_sum[product] * (power_sum[product] + 1);
                squared_sum[product] = squared_sum[i] / geometric[i] * geometric[product];
                break;
            } else {
                power_sum[product] = 1;
                geometric[product] = 1LL * primes[idx] * primes[idx] + 1;
                divisor_count[product] = 2 * divisor_count[i];
                squared_sum[product] = squared_sum[i] * squared_sum[primes[idx]];
            }
        }
    }
}

Additive and Multiplicative Functions

If f is an additive function and g(n) = C^f(n), then g is multiplicative.

Proof: g(1) = C^f(1) = C^0 = 1

For coprime positive integers n, m: g(n)g(m) = C^f(n+m) = C^f(nm) = g(nm)

Similarly, if f is completely additive, then g is completely multiplicative.