# Understanding Gauss Theorem:$n=\sum_{d|n}\phi(d)$

Gauss. For each positive integer $n\geq1$,$$n=\sum_{d|n}\phi(d)$$the sum being extended over all positive divisors of $n$.

Proof of this:

I need to understand all highlighted parts i.e.:

• Why number of integer in $S_d$ equal to number of positive integers not exceeding $n/d$ and relatively prime to $n/d$?
• And how that formula came (highlighted one)?

The first bullet holds because $f(x)=x/d$ is a bijection between $S_d$ and the set of integers relatively prime to $n/d$ and not exceeding it.
$$n=\sum_{d|n}|S_d|=\sum_{d|n}\phi(n/d)$$
where the first equality holds because the collection of $S_d$'s is a partition of $\{1,\ldots,n\}$
• ....ok, $S_d$ have $m's\leq n$, and let $gcd(m,n)=d$, now if we divide $n$ by $d$, then there is no comman factor between $m's$ and $n/d$, hence $gcd(m's,n/d)=1$, $S_d$ contains all such $m's$ which satisfy previous condition. So number of integers is $\phi(n/d)$. Is it correct? – mnulb Jan 3 '17 at 5:54