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

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)

• alternatively prove $\phi(nm) = \phi(n)\phi(m)$ when $gcd(n,m)=1$, prove $\sum_{n | d}\phi(d) = n$ when $n$ is a power of prime, and voila. Feb 18, 2016 at 2:38
• @user1952009 What if $n$ is not of prime power? Feb 18, 2016 at 2:45
• the properties of $\sum_{d | n} f(d)$ when $f$ is a multiplicative function ensures that it is enough to prove it when $n$ is a prime power. again if $c = ab$ with $gcd(a,b) = 1$ and the formula is true for $n=a$ and $n=b$ then $\sum_{d | c} \phi(d) = \sum_{d | ab} \phi(d) = \sum_{d_1 | a , \, d_2 | b} \phi(d_1 d_2) = \sum_{d_1 | a} \sum_{d_2 | b} \phi(d_1) \phi(d_2) = a b = c$ Feb 18, 2016 at 2:55

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.

• I don't see how this adds any clarification to the proof. Feb 18, 2016 at 1:59
• I added some more details. Feb 18, 2016 at 2:21

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)$.

• Why is $1\le m_1 \le n/d$? Feb 16, 2016 at 7:22
• @AlJebr Because $m \leq n$. Feb 16, 2016 at 7:24

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.$