Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2 / 1H (Number Theory)

The Euler totient function counts integers $1\le a\le n$ with $\gcd (a,n)=1$. The Möbius function has $\mu (1)=1$, is zero when a prime square divides $n$, and equals $(-1{)}^r$ when $n$ is a product of $r$ distinct primes. Consequentlybecause for $n>1$ the sum over squarefree divisors is $(1-1{)}^r$.

The Möbius inversion formula is $g(n)={\sum }_{d\mid n}\mu (d)f(n/d)$. Substituting the divisor sum defining $f$ and collecting the coefficient of $g(e)$ givesThis proof uses only finite sums, so no convergence hypothesis is needed.

Classifying $1,\dots ,n$ by their greatest common divisor with $n$ gives ${\sum }_{d\mid n}\phi (d)=n$: the class with greatest common divisor $n/d$ contains exactly $\phi (d)$ integers. Applying the Möbius inversion formula yieldsThe Riemann zeta function is $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\mathrm{Re}s>1$. Absolute convergence justifies multiplication of Dirichlet series. The divisor identity for the Möbius function gives $\sum \mu (n)n^{-s}=1/\zeta (s)$ there. For $\mathrm{Re}s>2$ both factors below converge absolutely, and their Dirichlet convolution is the Euler totient function: