Clarification on proof of the sum of Euler $\phi$ fcn: $\sum_{d|n}\phi(d)=n$

Question

---

In the proof, it says "clearly equals $\phi(n_1)$". I don't see how this is clear. I also don't see how this implies $n=\sum_{d|n}\phi(n/d)$.

Can someone please clarify this proof?

(from A Course in Combinatorics book by van Lint/Wilson, page 92)

Answer 1

Let $S_d$ consists of all $m\in N$ such that $(m,n)=d$. We may then partition $N$ as $N= \bigcup_{d\in\mathbb{N}} S_d$, which implies that $n=\lvert N \rvert=\sum_{d\in\mathbb{N}} \lvert S_d \rvert$.

Now note that $m\in S_d$ implies that $1\leq m\leq n$ and $(m/d,n/d)=1$. The number of such values is $\phi(n/d)$, by definition of the $\phi$ function. And so $\lvert S_d \rvert = \phi(n/d)$, implying that $n=\sum_{d|n} \phi(n/d)$ as desired.

Answer 2

Note that $\left(m,n\right)=d$, $1\leq m\leq n$ if and only if $\left(m_{1},n_{1}\right)=1$ with $m_{1}=m/d$ and $n_{1}=n/d$ and $1\leq m_{1}\leq n/d$. So there is a correspondence between the number $m$ and the integers $m_{1}$. But the number of $m_{1}$ is $\phi\left(n/d\right)$.

Answer 3

The standard number theory approach is to define a function $f$ on the positive integers as "multiplicative" if $f(ab) = f(a) f(b),$ whenever $\gcd(a,b) = 1.$ A multiplicative function is defined by its values at primes and prime powers.

Next is a lemma, needs careful proof, if $f$ is multiplicative, then so is $$ g(n) = \sum_{d |n} f(d). $$

It is also necessary to prove that $\phi$ really is multiplicative.

With all that done, your Theorem 10.2 comes down to showing the equation when $n$ is $1$ or a prime $p$ or a prime power $p^k.$ Note that $\phi(1) = 1, \phi(p) = p-1, \phi(p^2) = p^2 - p, \phi(p^3) = p^3 - p^2,$ and so on. You could call it induction on the exponent $k.$