1. Arithmetic functions: the cast
Any function $f : \mathbb{Z}_{\geq 1} \to \mathbb{C}$. Just that — a sequence indexed by the positive integers. The interesting ones are those whose values reflect something about the factorisation of $n$.
Four examples carry most of the weight of elementary multiplicative number theory.
$\tau(n)$ — number of divisors
$\tau(n)$ is the count of positive divisors of $n$. Some call it $d(n)$. For $n = 12 = 2^2 \cdot 3$ the divisors are $1, 2, 3, 4, 6, 12$, so $\tau(12) = 6$. A prime $p$ has $\tau(p) = 2$ (just $1$ and $p$); a prime power $p^k$ has $\tau(p^k) = k+1$.
$\sigma(n)$ — sum of divisors
$\sigma(n)$ is the sum of all positive divisors of $n$. For $n = 12$, $\sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28$. For a prime power, $\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \dfrac{p^{k+1} - 1}{p - 1}$ — a geometric series.
$\phi(n)$ — Euler's totient
$\phi(n)$ counts the integers in $\{1, 2, \dots, n\}$ that are coprime to $n$. For $n = 12$ the candidates coprime to $12$ are $1, 5, 7, 11$, so $\phi(12) = 4$. For a prime $p$, every smaller positive integer is coprime to $p$, so $\phi(p) = p - 1$.
$\phi$ governs the structure of $(\mathbb{Z}/n\mathbb{Z})^*$ — the multiplicative group of units modulo $n$ — and shows up everywhere from RSA key generation to roots of unity.
$\mu(n)$ — the Möbius function
$\mu$ is a sign-valued indicator of squarefreeness:
$$ \mu(n) = \begin{cases} 1 & \text{if } n = 1, \\ (-1)^k & \text{if } n \text{ is a product of } k \text{ distinct primes}, \\ 0 & \text{if any prime square } p^2 \text{ divides } n. \end{cases} $$So $\mu(1) = 1$, $\mu(2) = -1$, $\mu(6) = +1$ (two primes), $\mu(30) = -1$ (three primes), $\mu(12) = 0$ (because $4 \mid 12$). The point of $\mu$ is not its individual values — it's that summing it across divisors gives a delta:
$$ \sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1, \\ 0 & n > 1. \end{cases} $$That identity is the entire reason $\mu$ exists, and it's what powers Möbius inversion in §4.
| $n$ | factorisation | $\tau(n)$ | $\sigma(n)$ | $\phi(n)$ | $\mu(n)$ |
|---|---|---|---|---|---|
| $1$ | — | $1$ | $1$ | $1$ | $1$ |
| $2$ | $2$ | $2$ | $3$ | $1$ | $-1$ |
| $4$ | $2^2$ | $3$ | $7$ | $2$ | $0$ |
| $6$ | $2 \cdot 3$ | $4$ | $12$ | $2$ | $1$ |
| $8$ | $2^3$ | $4$ | $15$ | $4$ | $0$ |
| $12$ | $2^2 \cdot 3$ | $6$ | $28$ | $4$ | $0$ |
| $30$ | $2 \cdot 3 \cdot 5$ | $8$ | $72$ | $8$ | $-1$ |
2. Multiplicative functions
An arithmetic function $f$ with $f(1) = 1$ and
$$ f(mn) = f(m)\,f(n) \quad \text{whenever } \gcd(m, n) = 1. $$If the identity holds for all pairs (not just coprime ones), $f$ is called completely multiplicative.
The point is leverage. If $f$ is multiplicative and $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ is the prime factorisation, then
$$ f(n) = f(p_1^{a_1}) \cdot f(p_2^{a_2}) \cdots f(p_r^{a_r}). $$You only need to know $f$ on prime powers; the rest follows. That's an enormous reduction — instead of an infinite table indexed by $\mathbb{Z}_{\geq 1}$, you have a function defined on a much sparser set.
$\tau$, $\sigma$, $\phi$, and $\mu$ are all multiplicative. None of them is completely multiplicative (for example $\tau(4) = 3 \neq \tau(2)\tau(2) = 4$). The Dirichlet character $\chi$ and the constant function $1$ are completely multiplicative.
Values on prime powers
| $f$ | $f(p^k)$ | Why |
|---|---|---|
| $\tau$ | $k + 1$ | Divisors are $1, p, p^2, \dots, p^k$. |
| $\sigma$ | $\dfrac{p^{k+1} - 1}{p - 1}$ | Geometric sum of the divisors. |
| $\phi$ | $p^k - p^{k-1}$ | Of $p^k$ integers, exactly $p^{k-1}$ are multiples of $p$; the rest are coprime to $p^k$. |
| $\mu$ | $\mu(p) = -1$, $\mu(p^k) = 0$ for $k \geq 2$ | By definition. |
For $n = 12 = 2^2 \cdot 3$, just multiply the prime-power values:
$$ \tau(12) = \tau(2^2)\,\tau(3) = 3 \cdot 2 = 6, \qquad \sigma(12) = \sigma(2^2)\,\sigma(3) = 7 \cdot 4 = 28, \qquad \phi(12) = \phi(2^2)\,\phi(3) = 2 \cdot 2 = 4. $$The whole infinite function compresses into a recipe over primes.
3. Euler's totient: the product formula
Combining the multiplicative property with the prime-power formula $\phi(p^k) = p^k - p^{k-1} = p^k\bigl(1 - \tfrac{1}{p}\bigr)$ gives one of the cleanest identities in elementary number theory:
$$ \boxed{\;\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)\;} $$where the product runs over the distinct primes dividing $n$. Each prime divisor contributes a factor that strips out the multiples of that prime.
For example, $\phi(60) = 60 \cdot (1 - \tfrac{1}{2})(1 - \tfrac{1}{3})(1 - \tfrac{1}{5}) = 60 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 16$. Cross-check by brute count: the numbers in $\{1, \dots, 60\}$ coprime to $60$ are $1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59$ — sixteen of them.
That product formula is exactly inclusion–exclusion applied to the events "divisible by $p_1$", "divisible by $p_2$", and so on. Expanding the product reproduces the alternating sum you'd get by counting the complement. The compactness is the payoff of multiplicativity — and a preview of why the Möbius function (an inclusion–exclusion machine) plays such a central role.
4. Möbius inversion
Many counting problems naturally produce cumulative data: "how many things up to $n$ have property $P$, where $P$ is closed under refinement?" To recover the per-step counts you need a deconvolution. Möbius inversion is that deconvolution.
If $f$ and $g$ are arithmetic functions linked by
$$ f(n) = \sum_{d \mid n} g(d), $$then
$$ g(n) = \sum_{d \mid n} \mu\!\left(\tfrac{n}{d}\right) f(d). $$The two relations are equivalent — knowing either form lets you recover the other.
The mental picture: $f$ is a "totals" sequence, $g$ is the "increments" sequence, and $\mu$ provides the signed weights that recover $g$ from $f$. The identity $\sum_{d \mid n} \mu(d) = [n = 1]$ is what makes the whole machine work — it's the orthogonality relation that inverts divisor summation.
The canonical example: $\phi$ from $n$
Every integer in $\{1, \dots, n\}$ has a well-defined gcd with $n$, and that gcd is some divisor $d$ of $n$. Grouping by the value of $\gcd(k, n)$ gives the identity
$$ n = \sum_{d \mid n} \phi\!\left(\tfrac{n}{d}\right) = \sum_{d \mid n} \phi(d). $$So if you take $f(n) = n$ and $g(n) = \phi(n)$, the divisor-sum relation is $f = \sum g$. Möbius inversion immediately gives
$$ \phi(n) = \sum_{d \mid n} \mu\!\left(\tfrac{n}{d}\right) d. $$For $n = 6$: $\phi(6) = \mu(6) \cdot 1 + \mu(3) \cdot 2 + \mu(2) \cdot 3 + \mu(1) \cdot 6 = 1 - 2 - 3 + 6 = 2$. Correct.
If a problem hands you cumulative counts indexed by divisors and asks for the "primitive" or "exact" counts, Möbius inversion is almost always the right tool. The classic applications are counting primitive Pythagorean triples, primitive roots, irreducible polynomials over $\mathbb{F}_q$, necklaces of distinct period, and (one level up) cyclotomic polynomials.
5. Dirichlet series and the zeta function
Each arithmetic function has a natural generating series — not a power series, but a Dirichlet series:
$$ D_f(s) = \sum_{n=1}^{\infty} \frac{f(n)}{n^s}. $$The variable $s$ is complex; the series converges in some right half-plane. Dirichlet series multiply the way arithmetic functions convolve: $D_{f \ast g}(s) = D_f(s) D_g(s)$, where $(f \ast g)(n) = \sum_{d \mid n} f(d) g(n/d)$. So divisor-sum identities become product identities at the level of series.
The Riemann zeta function
The Dirichlet series of the constant function $\mathbf{1}(n) = 1$:
$$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}, \qquad \operatorname{Re}(s) > 1. $$Equivalently, by a foundational identity Euler discovered in 1737:
$$ \zeta(s) = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}. $$The equality of the sum and product is essentially the unique factorisation theorem in disguise. Expand each factor as a geometric series:
$$ \frac{1}{1 - p^{-s}} = 1 + p^{-s} + p^{-2s} + p^{-3s} + \cdots $$Multiplying across all primes and using the fact that every $n \geq 1$ has a unique factorisation produces each $1/n^s$ exactly once. The arithmetic structure of $\mathbb{Z}$ is the algebraic structure of the product.
The left side $\sum 1/n^s$ doesn't mention primes; the right side is entirely about primes. So any analytic fact you can prove about one side becomes an arithmetic fact about the other. This is the bridge that turns prime-counting problems into questions about a complex function — and ultimately into questions about where its zeros sit.
Useful Dirichlet identities
Once you have $\zeta$, many other Dirichlet series fall out cheaply:
$$ \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}, \qquad \sum_{n=1}^{\infty} \frac{\phi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}, \qquad \sum_{n=1}^{\infty} \frac{\tau(n)}{n^s} = \zeta(s)^2. $$The first one is Möbius inversion at the level of series — and it's also the statement that $\mu$ is the convolution inverse of the constant function $\mathbf{1}$.
Riemann (1859) showed that $\zeta(s)$, originally defined only for $\operatorname{Re}(s) > 1$, extends to a meromorphic function on all of $\mathbb{C}$, holomorphic except for a simple pole at $s = 1$. The values $\zeta(2) = \pi^2/6$ (the Basel problem) and $\zeta(-1) = -\tfrac{1}{12}$ (a famous regularised sum) sit inside this extension.
6. The Prime Number Theorem
Let $\pi(x) = \#\{\text{primes } \leq x\}$ be the prime-counting function. The driving question of analytic number theory: how fast does $\pi(x)$ grow?
Empirically, primes thin out — but slowly. Gauss conjectured around 1792 (and Hadamard and de la Vallée Poussin proved independently in 1896):
$$ \boxed{\;\pi(x) \sim \frac{x}{\ln x}\;} $$The symbol $\sim$ means the ratio tends to $1$ as $x \to \infty$. Equivalently, the density of primes near a large number $x$ is approximately $1/\ln x$. Pick a random integer near $10^{100}$ and the chance it's prime is roughly $1/230$.
Numerical check
| $x$ | $\pi(x)$ (exact) | $x / \ln x$ | ratio |
|---|---|---|---|
| $10^2$ | $25$ | $21.7$ | $1.151$ |
| $10^4$ | $1{,}229$ | $1{,}085.7$ | $1.132$ |
| $10^6$ | $78{,}498$ | $72{,}382.4$ | $1.085$ |
| $10^8$ | $5{,}761{,}455$ | $5{,}428{,}681$ | $1.061$ |
| $10^9$ | $50{,}847{,}534$ | $48{,}254{,}942$ | $1.054$ |
The ratio is creeping toward $1$ as advertised — but slowly. A sharper approximation is the logarithmic integral $\operatorname{Li}(x) = \int_2^x \tfrac{dt}{\ln t}$, which matches $\pi(x)$ to about $5$ digits already at $x = 10^9$. The PNT is equivalent to $\pi(x) \sim \operatorname{Li}(x)$; the version $\pi(x) \sim x/\ln x$ is the more memorable but slightly looser form.
The sketch of why $\zeta$ knows
Taking $\log$ of the Euler product gives
$$ \log \zeta(s) = \sum_p -\log(1 - p^{-s}) = \sum_p \sum_{k \geq 1} \frac{1}{k p^{ks}}, $$which to leading order is $\sum_p p^{-s}$ — a Dirichlet series whose coefficients are the indicator of primes. The behaviour of $\zeta$ near $s = 1$ (its pole) and on the line $\operatorname{Re}(s) = 1$ (no zeros there) is exactly what's needed to pull out $\pi(x) \sim x/\ln x$. The proof routes the question through complex analysis — which is why the subject is called analytic number theory.
7. The Riemann Hypothesis
$\zeta(s)$ has obvious "trivial" zeros at $s = -2, -4, -6, \dots$ (forced by its functional equation). All other zeros — the non-trivial ones — lie in the critical strip $0 < \operatorname{Re}(s) < 1$.
Every non-trivial zero of $\zeta$ has real part exactly $\tfrac{1}{2}$. Equivalently, all non-trivial zeros lie on the critical line $\operatorname{Re}(s) = \tfrac{1}{2}$.
RH is one of the seven Clay Mathematics Institute Millennium Problems, each carrying a $\$1{,}000{,}000$ prize. It has been verified numerically for the first $10^{13}$ non-trivial zeros, but a proof remains open.
Why does the location of the zeros matter? Because it controls the error term in the Prime Number Theorem. The PNT is equivalent to the statement that $\zeta$ has no zeros on the line $\operatorname{Re}(s) = 1$. The Riemann Hypothesis — pushing the zero-free region all the way to the critical line — would give the strongest possible error bound:
$$ \pi(x) = \operatorname{Li}(x) + O\bigl(\sqrt{x}\,\ln x\bigr). $$That bound is essentially as tight as it can be. Without RH, the best known error term is much weaker. Almost every refined statement about prime distribution — gaps between primes, primes in arithmetic progressions, Goldbach-style decompositions — has an "if RH, then …" sharpening.
The Generalised Riemann Hypothesis (GRH) extends the same claim to Dirichlet $L$-functions $L(s, \chi)$ — the natural relatives of $\zeta$ attached to Dirichlet characters. GRH is strictly stronger than RH and has its own array of conditional consequences (Miller's primality test being a famous one).
8. Common pitfalls
"Multiplicative" only requires $f(mn) = f(m)f(n)$ when $\gcd(m, n) = 1$. The four headline functions $\tau, \sigma, \phi, \mu$ are all multiplicative but none is completely multiplicative — for instance $\phi(4) = 2$, not $\phi(2)\phi(2) = 1$. Read the qualifier carefully.
In $\phi(n) = n \prod_{p \mid n}(1 - 1/p)$, the product runs over the distinct prime divisors of $n$, not with multiplicity. $\phi(12) = 12 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} = 4$ — only one factor of $(1 - \tfrac{1}{2})$, even though $4 \mid 12$.
Any statement involving $\zeta$ at $s = -1, 0, \tfrac{1}{2}$, etc. is about the analytic continuation, not the original series. The infamous "$1 + 2 + 3 + \cdots = -\tfrac{1}{12}$" is a value of the continuation; the series itself diverges at $s = -1$.
The critical strip is $0 < \operatorname{Re}(s) < 1$ — the region that contains all non-trivial zeros. The critical line is $\operatorname{Re}(s) = \tfrac{1}{2}$ — the midline. RH says the zeros are confined from the strip to the line.
Both approximate $\pi(x)$, but $\operatorname{Li}(x)$ is far better numerically. Don't confuse "$\pi(x) \sim x/\ln x$" (the looser, more memorable PNT) with "$\pi(x) \sim \operatorname{Li}(x)$" (equally true, much sharper in practice). The two are equivalent as asymptotic statements.
9. Worked examples
Example 1 · Compute $\phi(360)$
Step 1. Factor: $360 = 2^3 \cdot 3^2 \cdot 5$.
Step 2. Use the product formula:
$$ \phi(360) = 360 \cdot \left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{3}\right)\left(1 - \tfrac{1}{5}\right) = 360 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 96. $$Cross-check via multiplicativity. $\phi(8) = 4$, $\phi(9) = 6$, $\phi(5) = 4$, and $4 \cdot 6 \cdot 4 = 96$. ✓
Example 2 · Verify $\sum_{d \mid n} \mu(d) = 0$ for $n = 30$
Divisors of $30$: $1, 2, 3, 5, 6, 10, 15, 30$. Compute $\mu$ on each:
$\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(5) = -1$, $\mu(6) = 1$, $\mu(10) = 1$, $\mu(15) = 1$, $\mu(30) = -1$.
Sum: $1 - 1 - 1 - 1 + 1 + 1 + 1 - 1 = 0$. ✓
This is the orthogonality identity at $n = 30$ — and the engine behind Möbius inversion.
Example 3 · Recover $\phi$ from $n = \sum_{d \mid n} \phi(d)$ at $n = 12$
Divisors of $12$: $1, 2, 3, 4, 6, 12$. Möbius inversion gives
$$ \phi(12) = \sum_{d \mid 12} \mu(12/d) \cdot d. $$Computing each term:
- $d = 1$: $\mu(12) \cdot 1 = 0$
- $d = 2$: $\mu(6) \cdot 2 = 1 \cdot 2 = 2$
- $d = 3$: $\mu(4) \cdot 3 = 0$
- $d = 4$: $\mu(3) \cdot 4 = -1 \cdot 4 = -4$
- $d = 6$: $\mu(2) \cdot 6 = -1 \cdot 6 = -6$
- $d = 12$: $\mu(1) \cdot 12 = 1 \cdot 12 = 12$
Sum: $0 + 2 + 0 - 4 - 6 + 12 = 4$. ✓ Matches $\phi(12) = 4$.
Example 4 · Use PNT to estimate $\pi(10^{12})$
The PNT estimate is $\pi(x) \approx x/\ln x$. At $x = 10^{12}$:
$$ \frac{10^{12}}{\ln 10^{12}} = \frac{10^{12}}{12 \ln 10} \approx \frac{10^{12}}{27.63} \approx 3.62 \times 10^{10}. $$The true value is $\pi(10^{12}) = 37{,}607{,}912{,}018 \approx 3.76 \times 10^{10}$. About 4% high — the $\operatorname{Li}(x)$ form is much closer: $\operatorname{Li}(10^{12}) \approx 3.7607 \times 10^{10}$, off by only a few parts per million.
Example 5 · Verify the Dirichlet identity $\sum \mu(n)/n^s = 1/\zeta(s)$ at small $n$
The identity says $\zeta(s) \cdot \sum_n \mu(n)/n^s = 1$. Expanding the convolution, the coefficient of $1/n^s$ on the left is $\sum_{d \mid n} \mu(d)$, which equals $1$ if $n = 1$ and $0$ otherwise. So the product collapses to $1$ — exactly the identity. This is Möbius inversion lifted to Dirichlet series: $\mu$ is the convolution inverse of the constant function $\mathbf{1}$.