Multiplicative Functions

Suppose someone asks you: "how many numbers from 1 to a million are coprime to a million?" Checking all million candidates one at a time would take forever. But Euler's totient function \varphi has a shortcut hiding inside it: factor 1{,}000{,}000 = 2^6 \cdot 5^6, work out \varphi on each of those two small prime-power pieces, and just multiply the answers together. No million-step search required.

That shortcut isn't a coincidence about \varphi specifically — it's a whole family trait. Number theory is full of functions that take an integer and return something arithmetic about it: how many divisors it has, the sum of those divisors, how many numbers below it are coprime. A startling number of these share one magic property — they break apart along the prime factorisation. Such functions are called multiplicative, and once you know one is multiplicative, computing it on any number — however huge — reduces to computing it on a handful of prime powers.

Definition

An arithmetic function f (defined on positive integers) is multiplicative if f(1) = 1 and

f(mn) = f(m)\,f(n) \quad\text{whenever } \gcd(m, n) = 1.

Notice exactly what is and isn't being claimed. The rule fires only when m and n are coprime — share no common factor. It says nothing at all about f(mn) when they overlap. (If the multiplication rule holds for every pair m, n, coprime or not, the function is called completely multiplicative — a stronger, rarer property. Plain multiplicativity is the one that keeps showing up naturally, and it's the one this page is about.) We have already met one example: Euler's totient \varphi.

For contrast, an example of a completely multiplicative function is the identity function f(n) = n: it satisfies f(mn) = mn = f(m)f(n) for absolutely every pair m, n, coprime or not, since that's simply how multiplication works. \varphi is not that well-behaved — as the worked example below shows, it genuinely needs the coprimality condition to hold.

Why it's so powerful

A multiplicative function is completely determined by its values on prime powers. Given the factorisation n = p_1^{a_1}\cdots p_k^{a_k}, the prime-power pieces p_i^{a_i} are pairwise coprime, so they peel apart one multiplication at a time:

f(n) = f(p_1^{a_1})\, f(p_2^{a_2}) \cdots f(p_k^{a_k}).

So to understand f everywhere you only need to understand it on prime powers — turning a hard global question ("what is f of this giant number?") into several easy local ones ("what is f of this one small prime power?"). This one trick — factor first, then multiply small answers together — is the recurring engine behind almost everything in this stage of the course.

Worked example: multiplicativity holding

Let's check the property directly on \varphi. Take m = 3 and n = 4. They share no common factor (\gcd(3, 4) = 1), so multiplicativity predicts \varphi(12) = \varphi(3)\,\varphi(4). Let's verify both sides by direct count.

The two sides match perfectly: \varphi(12) = \varphi(3)\,\varphi(4) = 4. Multiplicativity delivered the right answer without ever listing all twelve numbers by hand.

Worked example: multiplicativity failing

Now try the same trick on a pair that is not coprime, to see why the condition really matters. Take m = 2 and n = 4, so mn = 8. This time \gcd(2, 4) = 2 \ne 1 — they share the factor 2.

4 \ne 2. The multiplication rule simply does not apply here, because m and n shared a factor. This isn't a special quirk of \varphi — it's exactly what the coprimality condition in the definition is there to rule out.

Worked example: three prime powers at once

The trick scales to as many prime factors as you like. Take n = 60 = 2^2 \cdot 3 \cdot 5 — three pairwise-coprime prime-power pieces. Multiplicativity says \varphi(60) = \varphi(4)\,\varphi(3)\,\varphi(5).

So \varphi(60) = 2 \times 2 \times 4 = 16. Counting the numbers from 1 to 60 coprime to 60 directly would mean checking sixty candidates by hand; multiplicativity gets the same answer, 16, from three tiny counts on 4, 3, and 5. The bigger n gets, the more this shortcut pays off — a number with ten different prime factors turns a search through billions of candidates into ten small local computations, multiplied together.

The single most common mistake with multiplicative functions is forgetting the coprimality condition and applying f(mn) = f(m)f(n) to any split of n — including ones where m and n share a factor. The worked example above shows exactly how that goes wrong: \varphi(2)\varphi(4) = 2, but the true value \varphi(8) = 4 is double that.

The safe habit is to always split a number into its distinct prime-power factors — p_1^{a_1}, p_2^{a_2}, \ldots — never into two arbitrary factors you happened to think of first. Prime powers built from different primes are automatically coprime, so that split is always safe. Splitting 8 as 2 \times 4 is tempting because it's arithmetically true, but both pieces are powers of the same prime, so the multiplicativity rule never applied there in the first place — 8 = 2^3 is already a single prime power, and should be evaluated as one piece, not split further.

What's coming next

\varphi is only the beginning. Two more famous multiplicative functions are next on the tour: the divisor functions — which count how many divisors a number has, or add them up — and the strange, elegant Möbius function, which only ever takes the values -1, 0, or 1 and quietly encodes inclusion–exclusion over a number's prime factors. Both are proved multiplicative the same way \varphi was above: check the definition on prime powers, then let multiplicativity carry the result to every other number for free.

It's tempting to think multiplicativity is a cute technical convenience. It's really something closer to a master key. Once you know a handful of functions are multiplicative — the totient, the divisor functions, the Möbius function, and others still to come — a single trick, "evaluate on prime powers, then multiply," lets you compute, tabulate, and prove theorems about all of them at once, no matter how large the input.

This is also why computer scientists building fast number-theory software lean so heavily on the unique prime factorisation of every integer: a sieve that tabulates values on small prime powers can cheaply build a table of \varphi, or the divisor-count function, or dozens of others, for every number up to some large bound in one pass. And the pattern reaches even further than arithmetic — this exact "independent-primes" structure is the seed of the Euler product for the Riemann zeta function, one of the deepest bridges in all of mathematics, connecting the primes to a single infinitely delicate function of a complex variable. All of that traces back to the humble rule f(mn) = f(m)f(n) for coprime m, n.