1. ## Elementary proof clarification.

I am reading through the proof of $$\phi(n)=\sum_{d| n}\mu(d)\frac{n}{d}$$ where $\phi$ is the Euler totient function and $\mu$ is the Mobius function.

$$\phi(n)=\sum_{k=1}^n \left[\frac{1}{(n,k)}\right]$$$$\phi(n)=\sum_{k=1}^n \sum_{d| (n,k)} \mu(d)$$$$=\sum_{k=1}^n\sum_{\substack{d|n \\ d|k}} \mu(d)$$
Up until this point, there are no problems, now letting $k=qd$, the next line is
$$\sum_{d|n}\sum_{q=1}^{n/d} \mu(d)$$

I am probably missing the obvious here, but I'm just not seeing how it got to that. Any help is appreciated.

2. ## Re: Elementary proof clarification.

Since k is going from 1 to n, how many times will d divide both k and n? Well, if d divides n, then there are $\dfrac{n}{d}$ values for $k$ such that $d|k$ and $d|n$. Those values are $dq$ where $q$ goes from 1 to $\dfrac{n}{d}$. So, if we instead consider only factors $d$ of $n$, we can figure out which values for $k$ will also be divisible by $d$. It is precisely when $k=qd$.

3. ## Re: Elementary proof clarification.

Thank you for the help SlipEternal, much appreciated.