# Understanding the proof of $\phi(n)=\sum_{d\mid n}\mu (d) \left(\frac{n}{d}\right)$.

A proof for the identity $\phi(n)=\sum_{d\mid n}\mu (d) \left(\frac{n}{d}\right)$ several times in this website. After studying the book Apostle's Analytic Number Theory and failed to understand I read through the answers in MSE also, but I can't understand them as well! The book is clear enough except for the step that I put a question remark which the text isn't convincing about.

Normally when summation is over two variables the order of summation doesn't matter, but here exchange of sum over k and over d is not understandable!

How the following equality holds: $$\sum_{d|1} \mu (d) + \sum_{d|2 \ \text{and} \ d|n} \mu (d) + \dots +\sum_{d|(n-1) \ \text{and} \ d|n} \mu (d) + \sum_{d|n} \mu (d) = \sum_{d|n} \mu (d) \dfrac{n}{d}?$$

Note. $(n,k) = \gcd (n,k)$. & $[x]$ is the smallest integer less than or equal to $x$.

Simple clear explanations would be much appreciated.

• I got it : $\varphi(n) = \sum_{k=1}^n \lfloor 1/gcd(n,k) \rfloor$ it is obvious from the definition. so write it as is (because $[\ .\ ]$ isn't $\lfloor . \rfloor$) – reuns May 14 '16 at 22:46
• the only one complicated step is $\sum_{k=1}^n \sum_{d | n,d | k} f(d) = \sum_{d|n} \sum_{k=1}^{n/d} f(d)$ – reuns May 14 '16 at 22:52
• It is no more than a $\sum\sum$ inversion. write $\sum_{k=1}^n \sum_{d | n, d | k} f(d) = \sum_{k=1}^n \sum_{d=1}^n f(d) 1_{d |n} 1_{d | k}$ and invert the two sums – reuns May 14 '16 at 22:54
• @user1952009, YesYesYes! That what I wanted to write as edit, the only step that I don't understand even with three "loosely speaking" lines explantion of the book. – user231343 May 14 '16 at 22:54
• You can also use Mobius inversion. – Qiaochu Yuan May 14 '16 at 23:33

we start from the definition : $$\varphi(n) = \sum_{k=1}^n 1_{ gcd(n,k)=1}$$

then a step requiring a proof : $$\sum_{k=1}^n \sum_{d |n, d| k} f(d) = \sum_{k=1}^n \sum_{d=1}^n f(d) 1_{d |n} 1_{d | k} = \sum_{d=1}^n \sum_{k=1}^n f(d) 1_{d |n} 1_{d | k} =\sum_{d=1}^n f(d) 1_{d |n} \sum_{k=1}^n 1_{d | k}$$

$$= \sum_{d|n} f(d)\sum_{k=1, d | k}^n 1 =\sum_{d|n} f(d) \sum_{q=1}^{n/d} 1 = \sum_{d |n} f(d) \frac{n}{d}$$

finally, once we know that $\sum_{d | n} \mu(d) = 1_{n=1}$, we use $$1_{ gcd(n,k)=1} = \sum_{d \ |\ gcd(n,k)} \mu(d)$$ and we get

$$\varphi(n) = \sum_{k=1}^n 1_{ gcd(n,k)=1} = \sum_{k=1}^n \ \sum_{d \ |\ gcd(n,k)} \mu(d) = \sum_{k=1}^n \sum_{d |n, d| k} \mu(d)$$

$$=\sum_{d |n} \mu(d) \frac{n}{d}$$

• @Edi : I wrote the whole proof, how I would have written it in the book – reuns May 14 '16 at 23:11
• About the 5th line: I don't understand how did you eliminate $1_{d|k}$? – user231343 May 14 '16 at 23:18
• I mean, l.h.s. says the q's such that k=qd and r.h.s. just sums over q's. – user231343 May 14 '16 at 23:22
• Now I have to figure out how f(d) passed through sum; yes, not explicit dependence on k but it is defined for d's that has 'relation' with k with d|k. I am sorry I am so stupid :( – user231343 May 14 '16 at 23:26
• @Edi : everything is good now ? – reuns May 14 '16 at 23:26