Questions: Arithmetic Functions and Multiplicativity

Question 1

What is d(72), the number of divisors of 72?

• A. 8
• B. 9
• C. 12
• D. 18

Answer: (C)

72 = 2³ × 3². By the product formula for the divisor function, d(72) = (3+1)(2+1) = 4 × 3 = 12. Each divisor is formed by independently choosing an exponent for 2 (0, 1, 2, or 3: four choices) and an exponent for 3 (0, 1, or 2: three choices). Multiplicativity lets you multiply these counts because 2³ and 3² are coprime. Trying to list divisors directly (1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72) confirms the answer.

Question 2

Suppose f is multiplicative and you know f(2) = 3, f(4) = 5, f(3) = 7. Which additional piece of information lets you compute f(12) without any further assumptions?

• A. f(2) alone, because multiplicativity means f(12) = f(2)⁴ / f(3)
• B. f(4) and f(3), because 12 = 4 × 3 and gcd(4, 3) = 1, so f(12) = f(4)·f(3) = 35
• C. f(2) and f(3), because 12 = 2² × 3 and f(12) = f(2)·f(2)·f(3) = 63
• D. All three values are needed and the answer is f(2)·f(4)·f(3)

Answer: (B)

Since 12 = 4 × 3 and gcd(4, 3) = 1, multiplicativity gives f(12) = f(4)·f(3) = 5 × 7 = 35. You need f(4) = f(2²), not just f(2), because a multiplicative function's values on prime powers are independent data — f(p²) is not determined by f(p) alone (only completely multiplicative functions satisfy f(p²) = f(p)²). Option C incorrectly applies complete multiplicativity, which is a stronger condition.

Question 3

Knowing f(p) for most prime p is sufficient to compute f(n) for most positive integer n, as long as f is multiplicative.

• T. True
• F. False

Answer: False

Multiplicativity requires knowing f on all prime *powers*, not just primes. For a prime power p^k with k ≥ 2, f(p^k) is independent data — it cannot be derived from f(p) unless f happens to be completely multiplicative (f(mn) = f(m)f(n) for ALL m, n, not just coprime pairs). For example, d(p) = 2 for every prime p, but d(p²) = 3, not 2² = 4. You need the value at each prime power separately.

Question 4

A multiplicative function on n is completely determined by its values on prime powers because the Fundamental Theorem of Arithmetic guarantees a unique factorization of every integer into coprime prime-power factors.

• T. True
• F. False

Answer: True

This is the structural reason multiplicativity is so powerful. Every n > 1 factors uniquely as p₁^a₁ · p₂^a₂ · … · pₖ^aₖ with distinct primes, and the factors are pairwise coprime. Applying f(mn) = f(m)f(n) repeatedly (valid since all factors are coprime) gives f(n) = f(p₁^a₁)·f(p₂^a₂)·…·f(pₖ^aₖ). Without unique factorization, this argument would fail — there would be multiple ways to factor n, potentially giving different values of f(n).

Question 5

Why does multiplicativity reduce the problem of computing an arithmetic function on all positive integers to computing it only on prime powers?

Model answer: The Fundamental Theorem of Arithmetic guarantees that every integer n > 1 factors uniquely into prime powers: n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ. These prime-power factors are pairwise coprime (gcd(pᵢ^aᵢ, pⱼ^aⱼ) = 1 for i ≠ j). Multiplicativity then gives f(n) = f(p₁^a₁)·f(p₂^a₂)·…·f(pₖ^aₖ) — a product of prime-power values. Since prime powers are much simpler objects than arbitrary integers (their structure is just p^k), the value of f there is usually given by a simple formula like a geometric series. Once those prime-power values are known, the function is determined everywhere.

This reduction is the core utility of multiplicativity. Computing d(n) for a random 20-digit number would be intractable by listing divisors, but factoring n and applying d(p^k) = k+1 at each prime power gives the answer immediately. The same pattern applies to σ(n), φ(n), and the Möbius function — multiplicativity is the lever that makes number-theoretic computation tractable.